ضرب زنجیره ای ماتریس

ضرب زنجیره ای ماتریس مسئله ای است که می تواند با استفاده از برنامه سازی پویا حل شود. وقتی یک توالی از ماتریس ها را داریم ما می خواهیم موثرترین راه را برای ضرب این ماتریس ها را با هم پیدا کنیم. مسئله اجرای ضرب ها نیست مسئله ترتیب اجرای ضرب ها است. ما انتخاب های زیادی داریم به خاطر این که ضرب ماتریس ها با هم در ارتباطند به عبارتی دیگر اهمیتی ندارد که ما چگونه جمله را پرانتز گذاری کنیم زیرا نتیجه یکسان خواهد بود. برای مثال اگر چهار ماتریس A،B،C،Dداشته باشیم به این صورت خواهد بود:
به هر حال ترتیب پرانتز گذاری جمله روی تعداد عملیات ریاضی ساده ای که برای محاسبهٔ نتیجه نیاز است تاثیر خواهد گذاشت. برای مثال فرض کنید A یک ماتریس ۱۰ × ۳۰ وB یک ماتریس ۳۰ ×۵ وCیک ماتریس ۵× ۶۰است سپس
واضح است که اولین روش بهینه است. حالا که ما مسئله را شناختیم چطور ما پرانتز سازی یک نتیجه یn ماتریس را مشخص کنیم. ما می توانیم هر کدام از پرانتز سازی ممکن را انجام بدهیم اما نیاز به زمان (O(۲ n دارد که برای nهای بزرگ خیلی آهسته خواهد بود.راه حل همان طور که خواهیم دید مسئله ر ا به مسائل کوچکتر مرتبط بشکنیم. به وسیلهٔ حل کردن مسائل کوچکتر برای یک بار و استفاده دوباره این راه حل ها ما می توانیم به طور قابل توجهی زمان مورد نیاز را کاهش دهیم این به عنوان برنامه سازی پویا شناخته شده است.