私は昨夜による動的計画法上の割り当てを持っていたが、私は最後の問題を解決する方法を理解できなかったので、私は未完成で、それを回すために持っていた動的計画法に

Question

を理解することができません：

状態を監視したいです高速道路で長さnマイル。高速道路の1マイルに監視装置を設置するには、 _iが必要です。監視装置間の最大距離はdマイル以下でなければなりません。すなわち、マイルi上に監視装置がある場合、マイルi + 1からマイルi + dまで（またはi + d> nの場合）の監視装置が1つ存在しなければならない。州はコストを最小限に抑える計画を望んでいる。コストの配列C [1..n]があるとします。

v _kを、kマイルの高速道路を想定し、マイルkの監視装置を仮定すると、最良の解決策のコストとしてください。 Cとdを指定すると、v 〜v _k-1の値がわかっている場合は、v _kの値を決定する方法を示します。これを数学的に書くことも、本のスタイルで擬似コードを提供することもできます。 k = 1からk = nまでのkのすべての可能な値を考慮する必要があることに注意してください。

このような問題は、試験に出てくると思いますが、どこで解決するかを少なくとも知りたいので、助けてください。

Answer 1

のステーションにモニターを設置する最小コストIとすぐ

I（各連続するステーションは、Dの距離以下であるように）未満であるいくつかの他の指標として[I] DPを定義でき（ - 、[D + 1からn] ... [N - 2] DP DP、[N - 1] DP、[n]はDP）我々の問題への答えは

分になり

があります最後のd索引で最後のモニターを持つための最小コスト。 - 、DP [I - 2]、... DP [I

DP [I] =分（DP [1 I]：次に、動的プログラミングのための漸化式が容易と見なすことができる

-d]）+ C [i] i番目のインデックスにモニタをインストールする場合は、コストC [i]でインストールします。また、前のdインデックスにモニタがあることを確認する必要があります。そのため、前回のd個のインデックスで2番目に最後のモニターをインストールする必要はありません。

ナイーブな方法で再帰をコード化すると、O（n * d）のように見えますが、二重終了キューを使用するスライディングウィンドウの最小アルゴリズムを使用すると、時間の複雑さを漸近的にO（n）に減らすことができます。

これは割り当て問題であるため、私は詳細を書いていません。この時点からフォローアップできるはずです。