الگوها در برنامه نویسی پویا - 2

سلب مسئولیت: روشی که در زیر توضیح داده شده است جهانی نیست، اما اغلب می تواند یک مشکل را حل کند یا به شما کمک کند تا راه حل مناسب را پیدا کنید.

اگر مشکلی از شما می‌خواهد که یک آرایه را به‌طور بهینه تخریب/جمع کردن/ادغام (یا مشابه) کنید، باید سعی کنید آن را با استفاده از برنامه‌نویسی پویا در زیربخش‌ها حل کنید.

بیایید 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] نه تنها به دو قسمت، بلکه به هر تعداد از آنها در نظر گرفته می شود.
 

سلب مسئولیت: روشی که در زیر توضیح داده شده است جهانی نیست، اما اغلب می تواند یک مشکل را حل کند یا به شما کمک کند تا راه حل مناسب را پیدا کنید.

اگر باید وجود جایگشت را در یک مشکل بررسی کنید، یا تعداد جایگشت‌های منطبق یا چیزی مشابه را بیابید، باید از برنامه‌نویسی زیرمجموعه پویا استفاده کنید.

پارامتر اصلی یک بیت ماسک خواهد بود که نشان می‌دهد کدام عناصر قبلاً در جایگشت گنجانده شده‌اند و کدام‌ها نیستند. همچنین اغلب مورد نیاز یک پارامتر دوم است که نشان می دهد کدام عنصر در آخرین بار گنجانده شده است.

اغلب جایگشت ها را می توان در زمینه مسیرها در نمودارها مشاهده کرد. بر این اساس، اجازه دهید یک مثال کلاسیک را در نظر بگیریم - مسئله مسیر همیلتونی.
مسیر همیلتونی یک مسیر ساده است که دقیقاً یک بار از هر رأس نمودار می گذرد. می توان آن را به سادگی به عنوان یک جایگشت طول n نشان داد، که در آن n تعداد رئوس است. ترتیب درون این جایگشت نشان دهنده ترتیب پیمودن رئوس در این مسیر است.

برای بررسی وجود یک مسیر همیلتونی در نمودار، اجازه دهید دینامیک dp[mask][last] را شروع کنیم - آیا مسیر ساده ای وجود دارد که رئوس علامت گذاری شده در بیت ماسک را دور زده و به آخرین راس ختم شود.
مقادیر اولیه dp[2ⁱ][i] = true و بقیه false خواهد بود، به این معنی که همیشه یک مسیر خالی وجود دارد که از هر یک از رئوس شروع می شود.
با داشتن مقدار true در dp[mask][last]، به معنای "توسعه مسیر" به جلو حرکت خواهیم کرد. یعنی به دنبال اعداد رئوس هایی می گردیم که در ماسک با صفر مشخص شده اند (هنوز در راه از آنها بازدید نکرده ایم) و در عین حال به گونه ای هستند که یک یال از آخرین تا این راس وجود داشته باشد (مسیر باید توسط یک لبه موجود گسترش یابد). یعنی dp[mask | را انجام می دهیم 2^k][k] = درست اگر dp[mask][last] = true AND mask & 2^k = 0 (راس k هنوز بازدید نشده است) و آخرین لبه وجود دارد -> k.
در نهایت، اگر یک مقدار واقعی در dp برای پارامترهای بیت ماسک همه یک‌ها و هر رأس آخر وجود داشته باشد، یک مسیر همیلتونی وجود دارد.