آروم آروم داریم وارد مبحثای نسبتا سخت میشیم و احتمالا روشون بیشتر وقت بذاریم .


برنامه نویسی پویا (به زبان ساده) : وقتی مسئله هامون به چندتا زیرمسئله تقسیم بشه و این زیرمسئله ها به هم وابسته باشن یا تکرار داشته باشن ،  این روش میتونه برای افزایش سرعت برنامه مون کمک زیادی بکنه ... 



-- ساده ترین مثال میتونه دنباله فیبوناچی باشه ، ما برای هر عددی نیاز به محاسبه دوتا عدد قبلش داریم که میتونیم یبار بصورت خطی همشون رو حساب کنیم و هر موقع لازم شد استفاده کنیم :

int f[MAX]={};

void fib()

{

    f[0]=f[1]=1;

    for (int i=2 ; i<MAX ; i++) f[i]=f[i-1]+f[i-2];

}


میتونیم بجای محاسبه ی کامل اعداد فیبوناچی ، فقط در موقع نیاز مقدارشون رو حساب کنیم که به این روش هم به یاد سپاری (memoize) میگن :

int f[MAX]={};

int fib(int n)

{

    if (n<2) return 1;

    if (f[n] != 0) return f[n];

    f[n] =  fib(n-1) + fib(n-2);

    return f[n];

ابتدای کار همه ی اعداد داخل آرایه صفرن ولی بعد از اینکه تابع مثلا با 5 صدا زده میشه ، فیبوناچی 2..5 محاسبه و ذخیره میشه و دفعات بعد اگه نیازی به هر کدوم از اینا باشه خط دوم برنامه جواب رو برمیگردونه و نیاز به محاسبه دوباره نداریم .

* با یه تست ساده میتونین تفاوت سرعت بیادسپاری رو برای میئله چک کنین ، همین برنامه رو یبار برای 100 اجرا کنین و بعد دوخط درشت شده رو پاک کنین و دوباره برای 100 برنامتون رو اجرا کنین .




-- مثال دوم میتونه جمع جزئی (partial sum) باشه :

فرض کنین یدونه آرایه به سایز n داریم و میخوایم m بار این سوال رو جواب بدیم که جمع ارقام اعضای داخل بازه [l,r] چند هستش ؟

روش ساده اینه که هربار این سوال پرسیده میشه یبار داخل آرایه حرکت کنیم و جمع رو بدست بیاریم ولی این روش میشه O_m*n . چون شاید همه ی پرسشا جمع کل اعضای آرایه رو بخواد.

بجای این کار میتونیم ت آرایه دیگه به سایز خود n بسازیم که داخل عضو i ام جمع ارقام 1 تا i از آرایه ی اصلی رو نگه داریم :


int dp[MAX];

dp[0] = 0;

for (int i=1 ; i<=n ; i++) dp[i] = dp[i-1] + a[i];


حالا با یه رابطه ساده میتونیم جمع اعضای داخل هر بازه ای رو جواب بدیم :

sum = dp[r] - dp[l-1]


مثال عددی :

a = { _ , 2 , 5 , 1 , 4}

dp = { 0 , 2 , 7 , 8 , 12 }

sum(2,4) = dp[4] - dp[1] = 12 - 2 = 10

sum(1,3) = dp[3] - dp[0] = 8 - 0 = 8 

...

این روش میشه O_n+m



آموزش سایت TopCoder خیلی خوب هستش . 


مسابقه از امشب شروع میشه .

( این پست احتمالا در طول هفته آپدیت شه )