سلب مسئولیت: روشی که در زیر توضیح داده شده است جهانی نیست، اما اغلب می تواند یک مشکل را حل کند یا به شما کمک کند تا راه حل مناسب را پیدا کنید.
اگر مشکلی از شما میخواهد که یک آرایه را بهطور بهینه تخریب/جمع کردن/ادغام (یا مشابه) کنید، باید سعی کنید آن را با استفاده از برنامهنویسی پویا در زیربخشها حل کنید.
بیایید dp[l][r] را بدست آوریم - پاسخ بهینه برای یک زیربخش با شاخصهایی از l تا r. محاسبه مجدد دینامیک بسیار وابسته به کار است، اما ایده های کلی زیر وجود دارد:
1) به عناصر افراطی l و r نگاه کنید. اگر به روش دیگری مطابقت یا تکمیل شوند، به احتمال زیاد امکان به روز رسانی مقدار dp[l][r] از طریق dp[l+1][r-1] وجود خواهد داشت. در غیر این صورت از طریق dp[l][r-1] یا dp[l+1[r].
2) اغلب اتفاق می افتد که قطعه [l;r] را نمی توان از طریق یک ساختار منفرد نشان داد. سپس لازم است تمام بخش های ممکن این زیربخش را به دو قسمت در نظر بگیریم، یعنی روی عنصر k از l تا r-1 تکرار کنیم و dp[l][r] را از طریق dp[l][k] و dp[ دوباره محاسبه کنیم. k+1][r]. در زیرمجموعه های کوچکتر نیز این بخش ها مرتب شده اند، بنابراین در واقع گزینه های تقسیم زیربخش [l;r] نه تنها به دو قسمت، بلکه به هر تعداد از آنها در نظر گرفته می شود.