سلب مسئولیت: روشی که در زیر توضیح داده شده است جهانی نیست، اما اغلب می تواند یک مشکل را حل کند یا به شما کمک کند تا راه حل مناسب را پیدا کنید.
اگر مشکل به این واقعیت ختم شود که لازم است آرایه را به صورت بهینه به زیربخش های غیر متقاطع (دنباله ای از عناصر متوالی) تقسیم کنیم (یا تعداد تقسیم های مناسب را بشماریم)، پس ارزش تلاش برای حل آن را دارد. با استفاده از برنامه نویسی پویا.
یک نمونه طرح راه حل به شرح زیر است:
dp[i] - پاسخ برای اولین عناصر i
شمارش dp[i]: از آنجایی که ما فقط اولین عناصر i را در نظر می گیریم، عنصر i-امین آخرین عنصر خواهد بود، به این معنی که این عنصر در آخرین زیربخش و در عین حال، سمت راست ترین عنصر در آنجا خواهد بود. بنابراین، می‌توانیم روی مرز سمت چپ آخرین زیربخش j تکرار کنیم. در فرآیند شمارش، مقدار این زیربخش را محاسبه می کنیم و اگر درست باشد، dp[i] را تا dp[j - 1] و مقدار زیربخش [j;i] را دوباره محاسبه می کنیم.
مشکل ساده زیر را در نظر بگیرید: با توجه به آرایه ای از اعداد صحیح، باید آن را به حداقل تعداد زیربخش های غیر متقاطع تقسیم کنید تا هر عدد در زیربخشی گنجانده شود و هر زیربخش دارای اعداد یکسان باشد. به عنوان مثال، برای یک آرایه 1 2 2 3 3 3 2 1 1، پارتیشن بهینه به صورت زیر است: [1] [2 2] [3 3 3] [2] [1 1]. این کار به سادگی با عبور از آرایه به راحتی حل می شود (همه عناصر متوالی مشابه را در یک زیربخش قرار می دهیم)، اما برای مثال آن را با استفاده از برنامه نویسی پویا حل می کنیم.
intn;
cin>> n
// آرایه را با 1-شاخص پر کنید
vector arr(n + 1);
برای (int i = 1; i <= n; i++)
cin>> arr[i];
// ابتدا +oo را روی مقادیر dp تنظیم کرد
vector dp(n + 1, 1000000000);
// آرایه ای با طول صفر نیازی به تقسیم ندارد، بنابراین پاسخ آن 0 است
dp[0] = 0;
// پاسخ dp[i] را در i صعودی بشمارید
برای (int i = 1; i <= n; i++) {
// در حال حاضر arr[i] آخرین عنصر است، بنابراین سمت راست ترین عدد در آخرین زیربخش خواهد بود.
// همه گزینه ها را برای جایی که آخرین زیربخش شروع شده است، حلقه بزنید
برای (int j = i; j > 0; j--) {
if (arr[j] != arr[i]) {
// اگر عنصری را ملاقات کنید که با آخرین عنصر برابر نیست، آن زیربخش شامل اعداد مختلفی خواهد بود و این با شرط مطابقت ندارد
// هیچ فایده ای برای ادامه وجود ندارد، زیرا با جابجایی مرز سمت چپ به چپ، این عنصر ناپدید نمی شود، بنابراین ما شکسته می شویم
زنگ تفريح؛
}
// تصور کنید آخرین زیربخش [j;i] بود
// بنابراین باید پارتیشن بهینه اولین عناصر j-1 را بگیرید و 1 را اضافه کنید (خود زیربخش [j; i])
dp[i] = min(dp[i]، dp[j - 1] + 1);
}
}
cout << dp[n];
اگر ممکن است عناصر به هیچ یک از زیربخش ها تعلق نداشته باشند، فقط باید گزینه مناسب را در نظر بگیرید، به عنوان dp[i] = dp[i - 1]