動的計画法のいくつかのメモと例を調べようとしていますが、すべてがどのように機能するかを理解するのに苦労しています。質問を投稿し、次に問題が発生していることを投稿します。
左から右にソートされた一連の点p1=（x1、y1）、...、pn =（xn、yn）（つまり、x1 <x2 <... <xn）と、1からnまでの数kが与えられます。 、左から右に向かうk個のエッジを持つp1からpnまでの折れ線を見つけ、チェーンまでのポイントの垂直距離の合計を最小化します。O（n ^ 3）時間で問題を解決する動的計画法アルゴリズムを設計します。サブ問題を設定し、必要なすべての基本ケースを指定し、再帰式を計算して、アルゴリズムの擬似コードを記述します。また、垂直差の計算に使用する関数f（a、b）が定義されているので、それを実装することを心配する必要はありません。f（a、b）として使用できます
サブ問題は次のように分割する必要があると思います。
C [i、j] = p1からpiまでのjエッジの折れ線で、垂直距離の合計を最小化します。
そして答えは次のようになります：C [n、k]
基本ケース：C [i、0] = 0
そして今、私は再帰式を思い付くのに少し苦労しています。私の最初の質問は、サブ問題を正しく分割しましたか？質問は私がしたように見えるヒントを与えますが、私は100％確信していません。私がそうなら、再帰式の導出を進める方法についてのヒントはありますか？
助けてくれてありがとう。