البرمجة الديناميكية (DP) تحل المشاكل التي تحتوي على overlapping subproblems وoptimal substructure عن طريق حساب كل مشكلة فرعية مرة واحدة وإعادة استخدام النتيجة. الأسلوبان هما memoization (من الأعلى إلى الأسفل) وtabulation (من الأسفل إلى الأعلى).
العودية الساذجة تعيد حساب نفس المشاكل الفرعية بشكل أسي. DP تخزن النتائج مؤقتاً، مما يقلل العمل الأسي إلى عمل متعدد الحدود.
from functools import lru_cache
@lru_cache(maxsize=None) # cache results automatically
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2) # each n computed once
def fib_table(n):
if n < 2:
return n
dp = [0, 1]
for i in range(2, n + 1):
dp.append(dp[i - 1] + dp[i - 2]) # build up from base cases
return dp[n]
| Memoization | Tabulation | |
|---|---|---|
| الاتجاه | عودية من الأعلى إلى الأسفل | تكرار من الأسفل إلى الأعلى |
| تحسب | الحالات المطلوبة فقط | جميع الحالات |
| الخطر | overflow في المكدس | لا شيء |
| المساحة | يمكن تقليلها | غالباً قابلة للاختزال إلى صفوف O(1) |
فيبوناتشي: من O(2ⁿ) الساذجة إلى O(n) زمن، O(n) (أو O(1)) مساحة.
استخدم DP عندما تتداخل المشاكل الفرعية. حدد الحالة و التكرار بعناية — هذا هو الجزء الصعب. إذا لم تتداخل المشاكل الفرعية، فإن divide-and-conquer العادي يكفي.
DP تحول المشاكل الأسية التي يستحيل حلها — المسارات الأقصر، تحرير المسافة، knapsack — إلى مشاكل فعالة.
مهارة تحديد الحالة و التكرار من بين أكثر المهارات المقدرة في مقابلات الخوارزميات.
هي تكمن وراء الأنظمة الحقيقية من أدوات diff إلى محاذاة السلاسل في المعلوماتية الحيوية.