תכנון דינמי - איך מפרקים בעיה לתת-בעיות?

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

שתי תכונות נדרשות

• Optimal Substructure - הפתרון האופטימלי בנוי מפתרונות אופטימליים של תת-בעיות
• Overlapping Subproblems - אותן תת-בעיות מופיעות שוב ושוב במהלך החישוב

דוגמה - סדרת פיבונאצ'י

// נאיבי - O(2^n)
function fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

// DP top-down (memoization) - O(n)
function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n < 2) return n;
  return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}

// DP bottom-up (tabulation) - O(n) זמן, O(1) זיכרון
function fibTab(n) {
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return n === 0 ? 0 : b;
}

Top-Down מול Bottom-Up

• Top-Down (Memoization) - רקורסיה + cache. אינטואיטיבי, מחשב רק תת-בעיות נחוצות
• Bottom-Up (Tabulation) - לולאה שממלאת טבלה מהקטן לגדול. נמנעת ממחסנית רקורסיה ולעיתים יעילה יותר בזיכרון

צעדים לפתרון בעיית DP

• זהו את התת-בעיה - מה משתנה בכל קריאה?
• הגדירו נוסחת רקורסיה (recurrence relation)
• זהו את מקרי הבסיס
• החליטו על שיטת מימוש (top-down/bottom-up)
• אופטימיזציה של זיכרון אם אפשר (לעיתים שומרים רק שורה אחרונה)

בעיות DP קלאסיות

• Knapsack (תרמיל גב) - בחירת פריטים עם משקל וערך
• LCS (Longest Common Subsequence) - תת-סדרה משותפת ארוכה
• Edit Distance - מרחק עריכה בין שתי מחרוזות
• Coin Change - מספר מינימלי של מטבעות לסכום נתון