الگوی برنامه‌نویسی پویا (Dynamic Programming - DP) اغلب به عنوان سخت‌ترین الگوی یادگیری شناخته می‌شود. دلیل این امر تنوع زیاد و ظرافت‌های (nuances) مسائل مختلفی است که تحت این دسته‌بندی قرار می‌گیرند.
مسائل برنامه‌نویسی پویا معمولاً شامل بهینه‌سازی یک راه‌حل با تفکیک آن به زیرمسائل هم‌پوشان (overlapping subproblems) هستند. هدف اصلی این الگو ذخیره نتایج این زیرمسائل و استفاده مجدد از آن‌ها برای جلوگیری از محاسبات اضافی است.
دو روش اصلی برای انجام برنامه‌نویسی پویا وجود دارد: بالا به پایین (Top-Down) و پایین به بالا (Bottom-Up).
۱. برنامه‌نویسی پویا از بالا به پایین (Top-Down DP)
در رویکرد بالا به پایین، شما از مسئله اصلی شروع می‌کنید و به صورت بازگشتی (recursively) زیرمسائل آن را حل می‌کنید.
- مکانیسم: راه‌حل زیرمسائل ذخیره می‌شود تا از حل مجدد همان زیرمسئله جلوگیری شود.
- ارتباط با پس‌گشت: ممکن است این رویکرد پیچیده به نظر برسد، اما شما در واقع از قبل می‌دانید که چگونه بخش زیادی از آن را انجام دهید، زیرا رویکرد بالا به پایین اساساً همان پس‌گشت (Backtracking) است، با این تفاوت که مرحله یادداشت‌برداری (Memorization) به آن اضافه شده است.
- یادداشت‌برداری (Memorization): یادداشت‌برداری یک مفهوم ساده است: ذخیره نتیجه فراخوانی تابع قبلی در یک دیکشنری (dictionary) و خواندن از آن زمانی که دقیقاً همان فراخوانی دوباره انجام می‌شود. این کار باعث می‌شود محاسبات تکراری حذف شوند.
۲. برنامه‌نویسی پویا از پایین به بالا (Bottom-Up DP)
در رویکرد پایین به بالا، شما ابتدا کوچک‌ترین زیرمسائل را حل می‌کنید و از راه‌حل‌های آن‌ها برای ساختن راه‌حل‌های مسائل بزرگ‌تر استفاده می‌کنید تا به راه‌حل نهایی برسید.
- ساختار: برنامه‌نویسی پویا از پایین به بالا معمولاً شامل پر کردن یک جدول (table) است که هر ورودی آن نشان‌دهنده راه‌حل یک زیرمسئله کوچک‌تر است.
- مکانیسم: شما با حالت‌های پایه (base cases) شروع می‌کنید و به صورت تکراری (iteratively) راه‌حل‌های زیرمسائل را به صورت تصاعدی بزرگ‌تر محاسبه می‌کنید تا به راه‌حل نهایی دست یابید.
- مزیت: این رویکرد از سربار بازگشت (recursion) و یادداشت‌برداری جلوگیری می‌کند و اغلب منجر به استفاده کارآمدتر از زمان و حافظه می‌شود.
- زمان استفاده: رویکرد پایین به بالا معمولاً زمانی استفاده می‌شود که وابستگی‌های بین زیرمسائل را بدانید و بتوانید راه‌حل را به صورت تکراری ساختاردهی کنید.
خلاصه
برنامه‌نویسی پویا فراتر از آن است که بتوان آن را به طور کامل در این توضیحات مختصر گنجاند، اما درک این نکته کلیدی است که DFS/Backtracking (بالا به پایین) به همراه یک لایه از حافظه‌سازی، و همچنین حل مسائل با استفاده از ساختار تکراری (پایین به بالا) بخش‌های اساسی این الگو را تشکیل می‌دهند.