برنامه‌نویسی پویا پیشرفته
DP پیشرفته: مسیرهای ماتریسی، طولانی‌ترین زیردنباله صعودی (LIS) با جستجوی دودویی و کوله‌پشتی کامل
سه مسئله پیشرفته DP
۱. مسیرهای ماتریسی (Unique Paths)
در گرید m×n از گوشه بالا-چپ به پایین-راست (فقط راست/پایین) چند مسیر؟
dp[i][j] = dp[i-1][j] + dp[i][j-1]
حالت پایه: سطر و ستون اول = ۱بینش: به هر خانه از بالا یا چپ می‌رسند! پاسخ = C(m+n−2, m−1) — ترکیبیاتی!
۲. طولانی‌ترین زیردنباله صعودی (LIS)
بلندترین دنباله صعودی «غیرپیوسته»: [10,9,2,5,3,7,101,18] ← [2,3,7,101] طول ۴.
O(n²): dp[i] = طول LIS پایان‌یافته در i؛ برای هر j
O(n log n) — ترفند tails: آرایه tails که tails[k] = کوچک‌ترین پایان LIS به طول k+1. برای هر عدد: جایگاهش در tails با جستجوی دودویی (اولین ≥ آن) جایگزین کن یا append! طول tails = طول LIS.
۳. کوله‌پشتی کامل (Unbounded)
برخلاف ۰/۱، هر آیتم بی‌نهایت‌بار قابل استفاده: سکه‌ها [1,2,5]، مبلغ ۱۱ ← کمترین سکه = ۳.
dp[0] = 0
dp[j] = min(dp[j], dp[j - coin] + 1) برای هر سکهتفاوت ظریف با ۰/۱: حلقه سکه «بیرون» و مبلغ «رو به جلو» ← استفاده مجدد مجاز!
جدول جمع‌بندی DP
| مسئله | حالت | پیچیدگی |
|---|---|---|
| مسیرهای ماتریسی | بالا + چپ | O(mn) |
| LIS ساده | max همه j کوچک‌تر | O(n²) |
| LIS بهینه | tails + دودویی | O(n log n) |
| کوله کامل | min روی سکه‌ها | O(n×amount) |
جمع‌بندی
- مسیرها: جمع از بالا و چپ
- LIS: O(n²) ساده یا O(n log n) با tails
- کوله کامل: سکه بیرون + مبلغ رو به جلو
- تشخیص الگو = نصف حل
این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.