برنامه نویسی پویا عمدتاً یک بهینه سازی ساده است بازگشت. هر جا یک راه حل بازگشتی دیدیم که برای ورودی های یکسان تماس های مکرر دارد، می توانیم آن را با استفاده از آن بهینه کنیم. برنامه نویسی پویا.
ایده این است که به سادگی نتایج مشکلات فرعی را ذخیره کنیم، به طوری که مجبور نباشیم بعداً در صورت نیاز آنها را دوباره محاسبه کنیم.
این بهینه سازی ساده پیچیدگی های زمانی را از نمایی به خطی کاهش می دهد.
به عنوان مثال، اگر یک راه حل بازگشتی ساده برای فیبوناچی بنویسیم، پیچیدگی زمانی نمایی به دست می آید و اگر آن را با ذخیره کردن راه حل های مسائل فرعی بهینه کنیم، پیچیدگی زمانی به خطی کاهش می یابد.
اگر با Big O Notation آشنا نیستید، در نهایت یک پست خواهم نوشت. اما به زبان ساده، نماد Big O برای طبقه‌بندی الگوریتم‌ها بر اساس چگونگی رشد زمان اجرا یا فضای مورد نیاز با افزایش اندازه ورودی استفاده می‌شود.
به عبارت دیگر:
برنامه نویسی پویا به سادگی یک تکنیک بهینه سازی با استفاده از کش است، برای ذخیره مقادیر محاسبه شده قبلی و برگرداندن این مقادیر هر زمان که نیاز باشد، بدون نیاز به محاسبه مجدد آنها.
ما این مقادیر را در کش (که معمولاً یادداشت نامیده می شود) با استفاده از ساختار داده هاشمپ برای دسترسی سریع ذخیره می کنیم.
انواع برنامه نویسی پویا
توجه به این نکته مهم است که دو رویکرد برای برنامه نویسی پویا وجود دارد. حفظ کردن و جدول بندی.
یکی از پرکاربردترین مثال‌ها هنگام معرفی برنامه‌نویسی پویا و بازگشت، دنباله فیبوناچی است.
به تصویر زیر دقت کنید:
در این تصویر ما Fibonnaci 5 را محاسبه می کنیم.
مقادیر برجسته شده محاسبات مکرر را نشان می دهد، که می توانیم هر زمان که برای اولین بار آنها را محاسبه می کنیم، آنها را در حافظه پنهان ذخیره کنیم، این اطمینان حاصل می کند که هر زمان که به این مقادیر نیاز بود آنها را دوباره محاسبه نمی کنیم.
این یک مثال ساده است. با این حال، برای اینکه دید وسیع تری از پیشرفت بزرگ برنامه نویسی پویا به شما ارائه دهیم، تصور کنید که باید فیبوناچی 30 را محاسبه کنیم، در اینجا چند محاسبه انجام می دهیم:
بدون DP: 2692537 محاسبات
با DP: 59 محاسبات
یک تفاوت بسیار شگفت انگیز، فکر نمی کنید؟
بیایید ببینیم چگونه می توانیم DP را با بهبود راه حل بازگشتی Fibonnaci پیاده سازی کنیم.
فیبوناسی بازگشتی
function fib(n) {
if (n < 2) {
return n;
} else {
return fib(n-1) + fib(n-2)
}
}
// Time Complexity - O(2^n)
Fibbonaci با حافظه
function dynamicFib(n, cache) {
let cache = cache || {};
if(cache[n]) return cache[n]
// base case
if (n < 2) return n;
return cache[n] = dynamicFib(n-1, cache[n]) + dynamicFib(n-2, cache[n])
}
// Time Complexity - O(n)
برای تمرین دانش جدید به دست آمده، من شما را تشویق می کنم که مشکل لیت کد زیر را حل کنید: بالا رفتن از پله ها
