سلام
DP روشی است که بر دو مبنای ، رابطه بازگشتی و نقطه شروع بنا شده .
این طور که برای حل سعی می کنیم مساله رو به زیر مساله های کوچک تر تقسیم کنیم و بعد از جواب های بدست اومده جواب مساله کلی رو بدست بیارم .
تا اینجای کار هیچ فرقی بین DP و روش "تقسیم و حل ( غلبه )" (Divide & Conquer ) نیست .
اما وجه تمایز این دو رویکرد در اینه که تو مسائل DP جواب زیر مساله هایی که حل کردیم رو نگه می داریم ( معمولا تو یه آرایه ) و بعد تو تکرار های بعدی از این مقادیر استفاده می کنیم ( برای جلوگیری از محاسبه دوباره ) .
برای اینکه این کار ما مفید باشه باید زیر مساله های تکراری داشته باشیم ، وگرنه خود D&C می تونه مساله رو حل کنه .
به عنوان مثال تابع فاکتوریل ( Factorial ) رو در نظر بگیرید .
یه همچنین تابعی میشه :
int Factorial ( int n )
{
if( n < 2 )
return 1;
return n * Factorial( n-1 );
}
تو همین تابع ساده فرض کنید می خوایم 5! رو بدست بیاریم . تمام مقادیر 1! و 2! و 3! و 4! و 5! ساخته میشن و از بین میرن .
حالا اگر دوباره مثلا 6! رو بخوایم حساب کنیم ، دوباره باید همه مقادیر قبلی رو محاسبه کنیم و ...
حالا اگر مقدار 5! که قبلا محاسبه کرده بودیم رو جایی نگه می داشتیم چی ؟
برای محاسبه 6! فقط کافی بود مقداری که قبلا محاسبه کردیم رو استخراج کنیم و جواب رو بدست بیاریم . توجه داشته باشید که با این کار از 4 بار فراخوانی تابع جلوگیری کردیم .
برای مقادیر بزرگتر و مسائل پیچیده تر این کار فوق العاده کمک می کنه .
چجوری این کارو انجام بدیم ؟
تابع رو یکم تغییر می دیم :
int DP[100] = {0};
int Factorial ( int n )
{
if( n < 2 )
return 1;
if( DP[n] != 0 )
return DP[n];
return DP[n] = n * Factorial( n-1 );
}
تو این حالت اگر DP[n] = 0 باشه ، یعنی هوز مقدارش رو حساب نکردیم پس مجبوریم تابع رو برای n-1 فراخوانی کنیم .
اگر DP[n] != 0 بود ، یعنی قبلا این تابع فراخوانی شده بوده و مقدارش حساب شده پس کافیه مقدار DP[n] رو برگردونیم . ( تو این حالت از فراخوانی زیرمساله های تکراری جلوگیری کردیم . )
توابع دیگه ای هم هستند که این شرایط رو دارند ، مثل دنباله فیبوناچی ( سعی کنید خودتون بنویسیدش )
تو حل مسائل DP باید برای حل تابع بازگشتی ارائه بدید . این توابع یه سری ورودی مستقل دارند و یه سری ورودی وابسته . برای اینکه بین زیر مساله های مختلف تمایز قائل بشیم باید طوری متغیر های مستقل رو انتخاب کنیم که اولا تمامی زیرمسائل رو شامل بشه و ثانیا زیر مساله ها با هم تداخل نداشته باشند .
برای ذخیره سازی زیر مسائل معمولا یه آرایه به اسم DP می گیریم که به تعداد ورودی های مستقل بُعد داره و هر بعد از اون یه اندازه بازه ای که اون ورودی می تونه تغییرات داشته باشه اندازه داره و تو هر سلول از این آرایه جواب متناظر با اون سلول قرار می گیره .
زمان مقدار دهی اولیه ، به هر سلول عددی رو نظیر می کنیم که هیچ وقت جواب تابع نباشه ( معمولا -1 )
مثلا تو تابع بالا ، فرض کردیم که مقادیر N! رو برای N < 100 نیاز داریم . پس ورودی تابع عددی بین 0 تا 99 خواهد بود و لذا اندازه DP رو 100 در نظر گرفتیم .
به عنوان مثالی پیچیده تر "ترکیب r تایی از n عضو" رو در نظر بگیریم .( n < 100 )
می دونیم این مقدار رو با ( C( n , r نشون میدن .
برای این مقدار رابطه بازگشتی زیر رو ارائه میدیم :
C( n , r ) = C( n-1 , r ) + C( n-1 , r-1 )
الان میبینیم که جواب مساله به دو متغیر مستقل ، وابسته شده پس برای ذخیره کردن زیرمساله ها به یه آرایه دوبعدی نیاز داریم . لذا برای محاسبه به صورت زیر عمل می کنیم .
int DP[100][100];
for( int i = 0 ; i < 100 ; i ++ )
{
DP[i][0] = DP[i][i] = 1;
for( int j = 1 ; j < i ; j ++ )
DP[i][j] = DP[i-1][j] + DP[i-1][j-1];
}
همین طور میشه برای سوال های پیچیده تر این کار رو کرد .
انواع DP :
بسته به شرایط و نوع تابع بازگشتی ای که پیدا می کنیم برای سوال می تونیم از 2 تکنیک موجود استفاده کنیم .
1. روش بالا به پایین : تو این روش هر زمان که احتیاج به زیر مساله کوچکتری داشتیم ، مقدارش رو محاسبه می کنیم . این روش معمولا با تابع بازگشتی( از نظر مفهوم برنامه نویسی ) پیاده سازی میشه . برای مثال اول ( فاکتوریل ) از این تکنیک استفاده کردیم .
خوبی : این تکنیک از نظر فهمیدن و نوشتن کد ساده است .
بدی :
کدش طولانی میشه .
چون از تابع بازگشتی استفاده می کنیم ، احتیاج به مقدار زیادی از stack داریم . برای تابع های بزرگ یا توابعی که عمق زیادی دارند نمیشه ازش استفاده کرد .( معمولا Stack Over Flow ) میشه .
اصطلاحا به تکنیکی که تو مثال اول استفاده کردیم ، Memoization یا به اختصار Memoize هم میگیم .
2. روش پایین به بالا : تو این روش شروع می کنیم از پایین با توجه به اندازه زیرمساله ها ، همه حالت هارو حساب می کنیم . می دونیم برای بدست آوردن مسائل کلی تر ، مساله رو به زیر مسائل کوچکتر تقسیم می کنیم . حالا چون بسته به اندازی کار کردیم ، حتما جواب زیر مساله ها رو داریم ( قبلا حساب کردیم ) و فقط کافیه از مقادیرشون استفاده کنیم .
تو مثال دوم ( ترکیب ) از این تکنیک استفاده کردیم .
خوبی : کدش کوتاهه و debug کردنش راحته .
بدی : مسائلی هستند که نیاز به تمام زیر مسائل کوچکتر ندارند ، فقط به بعضی از اونها نیاز دارند . تو این شرایط زمان اجرای کد طولانی میشه .
برای شروع چند یه سوال ساده از این مبحث کنید بد نیست .
علاوه بر این مطلب خوندن مطالب این مقاله و حل سوالاتی که توش مطرح کرده توصیه میشه .
اگر موردی هست که به نظرتون جا افتاده یا ... بگید تا اضافه کنم .
