מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי - דג הסלמון: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 108:
אפשר לראות ש{{קוד בשורה|Min-Time(1)}} נקרא הן מתוך {{קוד בשורה|Min-Time(2)}} והן מתוך {{קוד בשורה|Min-Time(98)}}. אומרים על כך שיש ''overlapping subproblems''.}}
==תזכור (Memoization)==
בנקודה זו אנו יודעים ש{{קוד בשורה|Min-Time}} נקרא שוב ושוב עם אותם הארגומנטים. מדוע שלא נשמור פשוט את התוצאה של כל קריאה בפעם הראשונה שחישבנו אותה עבור ארגומנט כלשהו? נעשה זאת כך. ראשית, נגדיר מערך גלובלי {{קוד בשורה|M}}, ונאתחל אותו ל<math dir = "ltr">\displaystyle n</math> ערכי {{קוד בשורה|Nil}}:
| |||