برنامه‌نویسی پویا (Dynamic Programming)

برنامه‌نویسی پویا: حل زیرمسئله‌های همپوشان با ذخیره‌سازی؛ memoization، tabulation، فیبوناچی و کوله‌پشتی

برنامه‌نویسی پویا چیست؟

Dynamic Programming (DP) برای مسائلی است که:

  1. زیرمسئله‌های همپوشان دارند — همان زیرمسئله چندبار محاسبه می‌شود
  2. ساختار بهینه دارند — جواب بهینه از زیرمسئله‌های بهینه ساخته می‌شود

راه‌حل DP: هر زیرمسئله را یک‌بار حل و جوابش را ذخیره کن!

انگیزه: فیبوناچی بازگشتی فاجعه است!

fib(5)
├── fib(4)
│   ├── fib(3) ...
│   └── fib(2) ...
└── fib(3)        ← تکراری!
    ├── fib(2)    ← تکراری!
    └── fib(1)

fib(50) بازگشتی ساده ≈ ۲⁵۰ فراخوانی — قرن‌ها زمان! اما با DP: فقط ۵۰ محاسبه.

دو رویکرد DP

۱. Memoization (بالا به پایین)

همان بازگشت + کش (memo): قبل از هر فراخوانی چک کن، بعد از هر محاسبه ذخیره کن.

۲. Tabulation (پایین به بالا)

جدول را از حالت‌های پایه به بالا پر می‌کنیم؛ بدون بازگشت — معمولاً کارآمدتر.

مسئله کوله‌پشتی (Knapsack)

معروف‌ترین مسئله DP: کوله با ظرفیت W و n آیتم (وزن، ارزش) — بیشترین ارزش با وزن ≤ W؟

فرمول بازگشتی:

best(i, w) = max(
    best(i-1, w),                      # آیتم i را نمی‌گیرم
    best(i-1, w - وزن[i]) + ارزش[i]    # آیتم i را می‌گیرم
)

حریصانه اینجا شکست می‌خورد — DP جواب بهینه تضمینی می‌دهد!

مراحل حل مسئله با DP

  1. زیرمسئله‌ها را تعریف کن (تابع بازگشتی بنویس)
  2. رابطه بازگشتی بین زیرمسئله‌ها پیدا کن
  3. حالت‌های پایه مشخص کن
  4. memoization یا tabulation پیاده کن
  5. پیچیدگی: معمولاً O(تعداد زیرمسئله × هزینه هر کدام)

کاربردهای واقعی

نکته: تشخیص DP: مسئله «بیشترین/کمترین/تعداد راه‌ها» می‌پرسد + انتخاب‌های فعلی روی آینده اثر دارد + زیرمسئله‌ها همپوشان‌اند. این سه‌گانه = پرچم DP!

جمع‌بندی

این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.

ابزارهای مرتبط