***2
در جلسات قبل گفته شد که روش تقسیم و حل یک روش از بالا به پایین است.
در این روش مسئله با سایز ورودی n را به انواع زیر مسائل می شکنیم ( انواع روش های شکستن را آزمایش می کنیم ) . این شکستن را ادامه می دهیم تا به مرحله ای برسیم که مسئله دیگر قابل شکستن نباشد و یا پاسخ بدیهی به نظر برسد .
معمولا با کوچک ترین و در نتیجه ساده ترین نمونه حل را آغاز می کنیم . سپس از ترکیب حل نمونه های کوچک تر حل نمونه های بزرگ تر به دست می آید و این روند ادامه می یابد تا سرانجام حل نمونه اصلی یا کامل حاصل شود .
این روش زمانی مفید است که معیار حریصانه ای وجود نداشته باشد و مسئله اصلی قابل شکستن باشد .
***3
انواع شکستن مسئله باعث می شود که تعدادی زیر مسائل تکراری تولید شود . هزینه حل یا محاسبه این تعداد از مرتبه نمایی است .
در روش برنامه نویسی پویا برای کاهش این مرتبه زمانی هر زیر مسئله در حافظه نگهداری شده و در مواقع تولید، زیر مسائل تکراری دیگر حل نمی شوند و تنها عمل واکشی اطلاعات صورت می گیرد .
تفاوت اصلی بین روش حریصانه و برنامه نویسی پویا آن است که در روش حریصانه فقط یک مجموعه ی انتخا ب ها ( جوابها ) تولید می شود در حالی که در برنامه نویسی پویا ممکن است مجموعه ی زیادی از انتخاب ها ( جوابها ) تولید شود.هر چند که مجموعه های شامل زیر مجموعه های بهینه نمی تواند بهینه باشند ( اگر اصل بهینه سازی برقرار باشد ) و بنا براین تا حد امکان نباید تولید شوند .
***4
حل مسئله به روش برنامه نویسی پویا
گام اول : مشخص کردن انواع روش های شکستن مسئله و ارائه این موضوع در یک طرح درخت واره ای
این فاز یکی از مهمترین فازها می باشد و یک طرح واحد نیست ولی بهینه ترین در نظر گرفته می شود .
گام دوم : کشف بهترین نوع ترکیب زیر مسائل کوچکتر
گام سوم : جلوگیری از محاسبات تکراری ، با طراحی یک جدول و ثبت جواب هر زیر مسئله در آن در ادامه کار اگر آن زیر مسئله دوباره تکرار شد از جدول استفاده می کنیم .
گام چهارم : پیاده سازی برنامه
گام پنجم : تحلیل زمانی / حافظه ای
***5
ضرب زنجیره ای ماتریس ها
مسئله اینست که ماتریس های زیر را به چه روشی با یکدیگر ضرب کنیم تا کمترین هزینه ضرب و جمع را بپردازیم ؟
M1 × M2 × M3 × … × Mn
مثال
فرض می کنیم چهار ماتریس داریم به طوری که سطر و ستون آن به ترتیب زیر باشد :