الفكرة
تقسيم المسألة لمسائل فرعية متداخلة، وحلّ كل واحدة مرّة واحدة وحفظ نتيجتها.
فيبوناتشي: من O(2ⁿ) إلى O(n)
Memoization (من الأعلى للأسفل):
def fib(n, memo={}):
if n < 2:
return n
if n in memo:
return memo[n]
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
Tabulation (من الأسفل للأعلى):
def fib(n):
dp = [0, 1]
for i in range(2, n + 1):
dp.append(dp[i - 1] + dp[i - 2])
return dp[n]
متى نستخدم DP؟
شرطان:
- مسائل فرعية متداخلة (نفس الحساب يتكرّر).
- بنية فرعية مثلى (حلّ الكلّ يُبنى من حلول الأجزاء).
أمثلة: حقيبة الظهر (knapsack)، أطول سلسلة جزئية مشتركة، عدّ الطرق.
🎯 التالي: الخوارزميات الجشعة.