dynammic programming یا برنامه نویسی پویا یعنی چی ؟

Question

سلام دوستان این dynammic programming چیه ؟  من 3 روز دیگه امتحان دارم هر چی میخونمش نمی فهمم !

Answer 1

در برنامه نویسی پویا وقتی چند زیرمسئله نتیجه یکسانی دارن لازم نیست که همشون رو حساب کنیم. فقط یکیش رو حساب میکنیم و تو بقیه از اون استفاده میکنیم.

مثلا تو دنباله فیبوناچی برای حساب کردن جمله 7 به جملات 5 و 6 نیاز داریم و برای حساب کردن جملات 5 و 6 تو هرکدوم نیاز داریم که جمله 4 رو حساب کنیم. در روش پویا فقط یک بار جمله چهارم حساب میشه و دفعات بعد دیگه محاسبه نمیشه بلکه از مقدارش که توی حافظه ذخیره شده استفاده میشه.

من که اینقدر میدونم 

Comments

تشکر به خاطر پاسخ کاملتون .

Answer 2

در راستای کامل کردن این سوال و جواب اقای bad programmer من دو کد تابع بازگشتی فیبوناتچی نوشتم که یکی به طور عادی محاسبه میکن و اون یکی اعداد رو ذخیزه میکنه که دوباره نیاز به محاسبه اون نباشه ، در اجرا فرق این دو الگریتم کاملا واضحه

کد اول که بهینه نیست :

#include <iostream>
using namespace std ;
unsigned long long F(int a)
{
    if ( a == 0 )
        return 0 ;
    if( a == 1 )
        return 1 ;
    else
        return F(a-1) + F(a-2) ;
}
int main()
{
    for ( int i = 0 ; i <= 90 ; i++ )
        cout << i << " : " << F(i) << endl ;
}

و کد دوم که بهینه تر هست :

#include <iostream>
#include <vector>
using namespace std ;
vector <unsigned long long> v ;
unsigned long long F(int a)
{
    if ( a < v.size() )
        return v[a] ;
    unsigned long long z = F(a-1)+F(a-2) ;
    v.push_back(z);
    return z ;
}
int main()
{
    v.push_back(0) ;
    v.push_back(1) ;
    for ( int i = 0 ; i <= 90 ; i++ )
        cout << i << " : " << F(i) << endl ;
}

پیشاپیش عذر میخوام اگه مشکلی هست و اشتباهی دارم

Comments

ممنون مثالتون خیلی کمک کرد .