حل مسائل داینامیک پروگرمینگ Dynamic Programming

داینامیک پروگرمینگ به طور عمده، بهینه سازی مثایل بازگشتیه (Recursion). راه‌حل‌های بازگشتی رو به این روش ما می‌تونیم بهینه کنیم. ایده به این صورته که نتیجه زیرمساله‌ها رو یک جایی ذخیره کنیم، در نتیجه بعدا که بهشون نیاز داریم، لازم نیست که دوباره حساب‌شون کنیم. این راهکار، پیچیدگی زمانی رو از تصاعدی به چندجمله‌ای (exponential to polynomial) تبدیل می‌کنه.

تکنینک‌های حل مسائل داینامیک پروگرمینگ:

۱- رویکرد بالا به پایین (Top-Down): این رویکرد از تکنیک memoization استفاده می‌کنه که شامل recusrsion و caching هست. بازگشتی، فرآینده فراخوانی پی‌درپی تابع‌هاست و کش کردن، پروسه ذخیره نتایج میانی هست.

۲- رویکرد پایین به بالا (Bottom-Up): این رویکرد از تکنیک tabulation استفاده می‌کنه که راهکار داینامیک پروگرمینگ رو پیاده‌سازی می‌کنه. به روش قبلی مساله رو حل می‌کنه ولی بدون بازگشتی (recursion). در این روش حلقه جایگزین بازگشتی میشه.

نمونه کد حل مساله فیبوناچی به روش memoization:

def fibonacci(n, cache={}):
    if n in cache:
        return cache[n]
    if n == 0:
        result = 0
    elif n == 1:
        result = 1
    else:
        result = fibonacci(n-1) + fibonacci(n-2)
    cache[n] = result
    return result

نمونه کد حل مساله فیبوناچی به روش tabulation:

int fibonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        std::vector<int> table(n + 1, 0);
        table[0] = 0;
        table[1] = 1;
        for (int i = 2; i <= n; i++) {
            table[i] = table[i-1] + table[i-2];
        }
        return table[n];
    }
}