מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/הדפסה יפה/שאלה

ברצוננו להדפיס פסקת טקסט בצורה יפה.

נתונות לנו $n$ מילים, תבנית:קוד בשורה. עלינו להחליט היכן לסיים כל שורה בפסקה, לפי הכללים הבאים:

1. בכל שורת טקסט יש מקום ל$M$ תווים (אין מילה בעלת יותר מ$M$ תווים).
2. יש להדפיס רווח יחיד בין כל שתי מילים באותה שורה.

תבנית:מבנה תבנית

אם בשורה יש $m^{\prime }$ תווים (כולל הרווחים בין המילים), אז יופי השורה הוא $\frac{1}{(M-m^{\prime }+1{)}^2}$. יופי הפסקה מוגדר כסכום היופי של השורות שלו, למעט השורה האחרונה.

תבנית:מבנה תבנית

אנא מצא אלגוריתם יעיל למציאת הפסקה היפה ביותר. הנח ש$n$ הוא משתנה גלובלי נתון, ושקיימת פונקציה תבנית:קוד בשורה המקבלת מספר $i$ ומחזירה את מספר התווים במילה ה$i$.