אם תיקח בעיה כלשהי ותתן לה פיתרון רקורסיבי, אז לפעמים בבעיות האלה יוצא שבעץ רקורסיה אתה מחשב בהרבה מקומות שונים את אותו הדבר.קח נגיד את פיבונצ'י: אם נניח מבקשים ממך למצוא את המס' פיבונצ'י הn-י אז הפתרון הרקורסיבי הרגיל יהיה:
אם N=1 או n=2 תחזיר 1
אחרת תחזיר
fib ( n - 1) + fib ( n-2 )
מה שיקרה זה שבעצם תבצע הרבה חישובים כפולים.. יהיה לך סוג של עץ כזה שכל מס' יחשב ע"י סכום 2 הקודמים וכל אחד מ2 הקודמים יחשב את ה2 קודמים שלו וככה הלאה.. ויהיו המון ענפים זהים.
הרעיון בתכנון דינמי, הוא בעצם לבנות משהו שהוא כמו מערך של מספרים פיבונצ'י ופשוט למלא אותו מההתחלה עד הסוף
נגיד אתה מאתחל את 2 התאים הראשונים ל1, ואז נגיד בתא השלישי אתה שם את הסכום של התא הראשון והשני , בתא הרביעי את הסכום של התא השני והשלישי וככה הלאה.. בסופו של דבר המטרה שלך לדעת מה הערך של התא הn-י. זמן הריצה של התהליך הזה הוא לינארי לעומת זמן הריצה האקספוננציאלי של הפיתרון הרקורסיבי הנאיבי.
היתרון של תכנון דינמי הוא שבד"כ הוא מפחית את זמן הריצה אבל הוא מגדיל את סיבוכיות הזיכרון.
באופן כללי כדי לפתור בעיה בתכנון דינמי בד"כ תצטרך לנסח נוסחת נסיגה לבעיה (fib ( n ) = fib (n-1) + fib ( n-2 ) ) ופשוט לבנות את טבלת הערכים מההתחלה עד הערך שאתה צריך (במקום ללכת מהערך שאתה צריך למטה).
גירסת הדפסה
סגן המנהל
מפקח
Winner
צל"ש
מומחה
