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

טכניקות תכנות דינמי

ישנן שתי גישות עיקריות לתכנות דינמיות: למעלה למטה ותחתית הגישה העליונה משתמשת memoization כדי לאחסן תוצאות של תת-בעיות במהלך טיול, הימנעות חישובים מחוסנים.הגישה התחתונה בונה פתרונות באופן גמיש מן תת-הסובייקטים הקטנים ביותר, מילוי שולחן כדי להגיע לתשובה הסופית.

סליחות ומימוש

יישום תכנות דינמי דורש להגדיר את המדינה, המייצגת תת-בעיה, ואת המעבר, המתאר כיצד למקם את הפתרון עבור מדינה ממדינות קודמות.בדרך כלל, שולחן או מערך משמש לאחסון תוצאות ביניים.

שימוש במקרים נפוצים

  • אלגוריתמים של נתיב קצר, כגון Dijkstra's & Floyd-Warshall
  • בעיות סכינים
  • המונחים: bioinformatics
  • עצי חיפוש בינאריים
  • שינוי בעיות