במדעי המחשב, שיטת התכנון הדינמי לבניית אלגוריתם, שהוצגה לראשונה בשנת 1953 על ידי ריצ'רד בלמן, היא שיטה לפתרון בעיות בעלות תת-מבנה מיטבי (Optimal substructure) שאי אפשר לפתור אותן באופן יעיל בשיטת הפרד ומשול נאיבית. שיטת הפרד ומשול נאיבית פותרת בעיה על ידי חלוקתה לתת-בעיות, הנפתרות בתורן על ידי חלוקתן לתת-בעיות קטנות אף יותר, עד שמתקבלות בעיות קטנות מספיק שניתן לפתור אותן באופן ישיר.

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

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

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

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

1. מציגים פתרון רקורסיבי לבעיה.
2. מגלים כי זמן ריצת האלגוריתם הרקורסיבי (הפועל "מלמעלה למטה") הוא מעריכי.
3. מגלים כי מספר תת-הבעיות הקיימות הוא פולינומי, והסיבה לסיבוכיות המעריכית היא קריאות חוזרות לאלגוריתם עבור אותה תת-בעיה שכבר נפתרה.
4. פותרים את הבעיה על ידי פתרון כל תת-הבעיות – ממקרי הקצה שפתרונותיהם ידועים מראש ("כלפי מעלה") – עד שמגיעים לבעיה המקורית.

סדרת פיבונאצ'י היא סדרה המוגדרת באמצעות נוסחת הנסיגה הבאה:

${\displaystyle \ fib(n)=fib(n-1)+fib(n-2)}$

כאשר שני האיברים הראשונים בסדרה נתונים:

${\displaystyle \ fib(1)=fib(2)=1}$

חישוב רקורסיבי, "מלמעלה למטה", של ${\displaystyle \ fib(n)}$ באמצעות כלל הנסיגה אפשרי, אבל בזבזני מאוד, מאחר שערכי הסדרה הראשונים יחושבו פעמים רבות (מספר מעריכי של פעמים).

לדוגמה, נחשב בצורה זו את האיבר החמישי בסדרה בצורה זו:

קל לראות בדוגמה זו שהערך ${\displaystyle \ fib(2)}$ מחושב שוב ושוב פעמים רבות, ושהחישוב ייעשה בלתי יעיל להפליא עבור ערכים גדולים של ${\displaystyle \ n}$.

אלגוריתם תכנון דינמי לפתרון הבעיה יעבוד בכיוון ההפוך – הוא ינוע מערכי הקצה ${\displaystyle \ fib(1),fib(2)}$ לערך הרצוי על ידי חישוב סדרתי של כל מספרי פיבונאצ'י עד אליו. למשל עבור הדוגמה הקודמת שלנו, כאשר ${\displaystyle \ n=5}$ האלגוריתם יפעל כך:

1. חישוב ${\displaystyle \ fib(3)}$ באמצעות ${\displaystyle \ fib(1),fib(2)}$ הנתונים.
2. חישוב ${\displaystyle \ fib(4)}$ באמצעות ${\displaystyle \ fib(3)}$ (שחושב בצעד הקודם) ו-${\displaystyle \ fib(2)}$ (הנתון).
3. חישוב ${\displaystyle \ fib(5)}$ באמצעות ${\displaystyle \ fib(4),fib(3)}$ (שחושבו בצעדים הקודמים).

ניתן לשים לב שבעוד שהאלגוריתם הרקורסיבי שתואר קודם לכן ביצע 9 קריאות רקורסיביות, האלגוריתם החדש ביצע 3 צעדים בלבד, מאחר שחישב את כל אחד מהערכים ${\displaystyle \ fib(3)...fib(5)}$ פעם אחת בלבד.

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

• תכנות דינמי, דף שער בספרייה הלאומית