מהי תכנות דינמי?

תכנות דינמי (DP) הוא טכניקה אלגוריתמית המשמשת לפתרון בעיות אופטימיזציה באמצעות פירוקן לתת־בעיות פשוטות יותר ושימוש חוזר בפתרונות של אותן תת־בעיות כדי לפתור את הבעיה המקורית.

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

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