***3
برنامه نویسی پویا، از این لحاظ که نمونه به نمونه های کوچکتر تقسیم می شود ، مشابه روش تقسیم و حل است ولی در این روش ، نخست نمونه های کوچک تر را حل می کنیم ، نتایج را ذخیره می کنیم و بعدا هر گاه به یکی از آن ها نیاز پیدا شد، به جای محاسبه دوباره کافی است آن را بازیابی کنیم.
***4
nمراحل بسط یک الگوریتم برنامه نویسی پویا به شرح زیر است:
1- ارائه یک ویژگی بازگشتی برای حل نمونه ای از مسئله .
2- حل نمونه ای از مسئله به شیوه جزء به کل با حل نمونه های کوچک تر.
***22
حل بهینه ، سومین مرحله از بسط یک الگوریتم برنامه نویسی پویا برای مسائل بهینه سازی است. مراحل بسط چنین الگوریتمی به شرح زیر است:
***23
ارائه یک ویژگی بازگشتی که حل بهینه ی نمونه ای از مسئله را به دست می دهد.
2- محاسبه مقدار حل بهینه به شیوه ی جزء به کل.
3- بنا کردن یک حل نمونه به شیوه ی جزء به کل.
***24
هر مسئله بهینه سازی را نمی توان با استفاده از برنامه نویسی پویا حل کرد چرا که باید اصل بهینگی در مسئله صدق کند.
اصل بهینگی در یک مسئله صدق می کند اگریک حل بهینه برای نمونه ای از مسئله ، همواره حاوی حل بهینه برای همه ی زیر نمونه ها باشد.
***26
هدف بسط الگوریتمی است که ترتیب بهینه را برای n ماتریس معین کند.
ترتیب بهینه فقط به ابعاد ماتریس ها بستگی دارد.
علاوه بر n ، این ابعاد تنها ورودی های الگوریتم هستند.
این الگوریتم حداقل به صورت نمایی است