سلب مسئولیت: روشی که در زیر توضیح داده شده است جهانی نیست، اما اغلب می تواند یک مشکل را حل کند یا به شما کمک کند تا راه حل مناسب را پیدا کنید.
اگر مجموعه‌ای از شکاف‌ها روی یک محور (معمولاً محور زمانی یا شاخص‌های یک آرایه) قرار دارند و باید برخی از آنها را به‌طور بهینه انتخاب کنید تا شکاف‌های انتخاب‌شده با هم تلاقی نکنند، باید از برنامه‌نویسی پویا استفاده کنید. .
طرح حل تقریبی:
در ابتدا، شکاف های موجود را بر اساس حاشیه سمت راست مرتب می کنیم. بیایید دینامیک زیر را شروع کنیم: dp[i] - پاسخ اولین فواصل i.
ما به صورت زیر دوباره محاسبه می کنیم: ابتدا وضعیتی را در نظر بگیرید که این بازه استفاده نمی شود، سپس فقط dp[i] = dp[i-1]. توجه داشته باشید که این تضمین می کند که مقادیر dp[i] با رشد i کاهش نمی یابد. و این منطقی است، زیرا. با اضافه کردن یک شکاف جدید، نمی‌توانیم پاسخ جهانی را بدتر کنیم: یا به سادگی شکاف جدید را نادیده می‌گیریم، یا با استفاده از آن یک نوع سودآورتر می‌سازیم. حال، اگر بخواهیم از شکاف i-ام استفاده کنیم، می‌توانیم از آن شکاف‌هایی استفاده کنیم که مرزهای سمت راست آنها کمتر از مرز چپ شکاف فعلی است، زیرا باید مجموعه‌ای از شکاف‌های غیر همپوشانی را انتخاب کنیم. برای انجام این کار، ابتدا شکاف ها را بر اساس حاشیه سمت راست مرتب کردیم تا اکنون بتوانیم موقعیت مورد نیاز را به طور موثر پیدا کنیم. در صورت امکان می توان این کار را به صورت تحلیلی انجام داد، اما در حالت کلی می توان با جستجوی بینایی شکافی را یافت که مرز سمت راست آن کمتر از مرز سمت چپ فعلی و در عین حال حداکثر ممکن است. یکی ما می خواهیم مرز مناسب را به دلایل حریصانه به حداکثر برسانیم، زیرا همانطور که من رشد می کنم، پاسخ فقط می تواند افزایش یابد. بر این اساس، موقعیت p مورد نیاز را پیدا کرده و dp[i] را تا dp[p] و بازه i-ام دوباره محاسبه می‌کنیم.