آروم آروم داریم وارد مبحثای نسبتا سخت میشیم و احتمالا روشون بیشتر وقت بذاریم .
برنامه نویسی پویا (به زبان ساده) : وقتی مسئله هامون به چندتا زیرمسئله تقسیم بشه و این زیرمسئله ها به هم وابسته باشن یا تکرار داشته باشن ، این روش میتونه برای افزایش سرعت برنامه مون کمک زیادی بکنه ...
-- ساده ترین مثال میتونه دنباله فیبوناچی باشه ، ما برای هر عددی نیاز به محاسبه دوتا عدد قبلش داریم که میتونیم یبار بصورت خطی همشون رو حساب کنیم و هر موقع لازم شد استفاده کنیم :
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 خیلی خوب هستش .
مسابقه از امشب شروع میشه .
( این پست احتمالا در طول هفته آپدیت شه )