קודם כל איך אני מצליח לבנות נוסחאות לדבר הזה?

ואיך פותרים שאלות בנושא זה

קח נגיד את פיבונצ'י: אם נניח מבקשים ממך למצוא את המס' פיבונצ'י הn-י אז הפתרון הרקורסיבי הרגיל יהיה:

אם N=1 או n=2 תחזיר 1
אחרת תחזיר
fib ( n - 1) + fib ( n-2 )

מה שיקרה זה שבעצם תבצע הרבה חישובים כפולים.. יהיה לך סוג של עץ כזה שכל מס' יחשב ע"י סכום 2 הקודמים וכל אחד מ2 הקודמים יחשב את ה2 קודמים שלו וככה הלאה.. ויהיו המון ענפים זהים.

הרעיון בתכנון דינמי, הוא בעצם לבנות משהו שהוא כמו מערך של מספרים פיבונצ'י ופשוט למלא אותו מההתחלה עד הסוף
נגיד אתה מאתחל את 2 התאים הראשונים ל1, ואז נגיד בתא השלישי אתה שם את הסכום של התא הראשון והשני , בתא הרביעי את הסכום של התא השני והשלישי וככה הלאה.. בסופו של דבר המטרה שלך לדעת מה הערך של התא הn-י. זמן הריצה של התהליך הזה הוא לינארי לעומת זמן הריצה האקספוננציאלי של הפיתרון הרקורסיבי הנאיבי.

היתרון של תכנון דינמי הוא שבד"כ הוא מפחית את זמן הריצה אבל הוא מגדיל את סיבוכיות הזיכרון.

המון פעמים ניעזר במטריצה כדי לחשב את הערכים השונים במעלה פתרון הבעייה המקורית.