免責事項: 以下に説明する方法は普遍的なものではありませんが、多くの場合、問題を解決したり、適切な解決策を見つけるのに役立ちます.
ある軸 (通常は時間軸または配列のインデックス) 上に一連のギャップがあり、選択したギャップが交差しないように最適な方法でそれらの一部を選択する必要がある場合は、動的プログラミングを使用してみる必要があります。 。
おおよその解決スキーム:
最初に、利用可能なギャップを右の境界線で並べ替えます。次のダイナミクスを開始しましょう: dp[i] - 最初の i 間隔の答え。
次のように再計算します。まず、この間隔が使用されない状況を考慮し、次に dp[i] = dp[i-1] だけを計算します。これにより、i が増加しても dp[i] の値が減少しないことが保証されることに注意してください。そして、これは論理的だからです。新しいギャップを追加しても、全体的な答えを悪化させることはできません。単に新しいギャップを無視するか、それを使用してより収益性の高いバリアントを構築するかのどちらかです。ここで、i 番目のギャップを使用したい場合は、重複しないギャップのセットを選択する必要があるため、現在のギャップの右境界が左境界より小さいギャップを使用できます。これを行うために、最初に右側の境界線でギャップを並べ替えたので、必要な位置を効率的に見つけることができるようになりました。これは可能であれば分析的に行うことができますが、一般的な場合は、ビンサーチを使用してギャップを見つけることが可能です。そのギャップの右境界は現在の境界の左境界より小さく、同時に可能な限り最大の境界になります。一。貪欲な理由から、適切な境界線を最大化したいと考えています。私が成長するにつれて、答えは増えるだけです。したがって、必要な位置 p を見つけて、dp[i] から dp[p] および i 番目の間隔を再計算します。