動的計画法を理解したい

動的計画法

与えられた問題に対して部分問題に上手に分割し、メモ化しながら与えられた問題を解く方法のことを言います。解決できる問題の幅が広いが習得するのが難しいです。問題の分解方法に注目して練習を積み重ねます。

AtCoder Educational DP Contest A-Frog 1 問題

N個の足場があって,i=(0,1,2,3,4...,N-1)番目の高さはh_iで与えられます。最初0番目の足場にカエルがいて、以下のいずれかの行動を繰り返してN-1番目の足場を目指します。
・足場iから足場i+1へと移動する(コストは|h_i-h_{i+1}|)
・足場iから足場i+2へと移動する(コストは|h_i-h_{i+2}|)
カエルがN-1番目の足場にたどり着くまでに要するコストの総和の最小値を求めてください。

example

N=8,h=(3,4,9,5,10,8,5,12)
カエルは「次の足場に行く」と「1個飛ばした足場に行く」という2つの選択肢があります。
足場間の移動を「矢印」で、その時のコストを「重み」として表現します。
そうすると、以下のように問題を書き換えることができます。
問題
頂点0から頂点7まで移動するとき、たどった各辺の重みの総和の最小値を求めてください。
この問題を7つの問題に分けます。
問題0:0に移動する時の重みの総和の最小値を求めなさい
問題1:0→1に移動する時の重みの総和の最小値を求めなさい
問題2:0→2に移動する時の重みの総和の最小値を求めなさい
問題3:0→3に移動する時の重みの総和の最小値を求めなさい
問題4:0→4に移動する時の重みの総和の最小値を求めなさい
問題5:0→5に移動する時の重みの総和の最小値を求めなさい
問題6:0→6に移動する時の重みの総和の最小値を求めなさい
問題7:0→7に移動する時の重みの総和の最小値を求めなさい

解説

「1つ進んだ時の重みをp」「2つ進んだ時の重みをq」とすると
問題0の解は、進んでいないので0
問題1の解は、問題0の解+p
問題2の解は、(問題1の解+p)と(問題0の解+q)を比較した時の小さい方
問題3の解は、(問題2の解+p)と(問題1の解+q)を比較した時の小さい方
問題4の解は、(問題3の解+p)と(問題2の解+q)を比較した時の小さい方
問題5の解は、(問題4の解+p)と(問題3の解+q)を比較した時の小さい方
問題6の解は、(問題5の解+p)と(問題4の解+q)を比較した時の小さい方
問題7の解は、(問題6の解+p)と(問題5の解+q)を比較した時の小さい方

これを最小コストの配列dpを使って表すと

問題0の解は、dp[0]=0
問題1の解は、dp[1]=dp[0]+p
問題2の解は、dp[2]=min((dp[1]+p),(dp[0]+q))
問題3の解は、dp[3]=min((dp[2]+p),(dp[1]+q))
問題4の解は、dp[4]=min((dp[3]+p),(dp[2]+q))
問題5の解は、dp[5]=min((dp[4]+p),(dp[3]+q))
問題6の解は、dp[6]=min((dp[5]+p),(dp[4]+q))
問題7の解は、dp[7]=min((dp[6]+p),(dp[5]+q))

これをコードにすると

#include <bits/stdc++.h>
using namespace std;
const long long INF=1LL<<60;

int main(){
    //入力
    int N;
    cin>>N;
    vector<long long> h(N);
    for (int i=0;i<N;++i)cin>>h[i];

   //重みの最小値を格納する配列dpを定義
    vector<long long> dp(N,INF);
    dp[0]=0;

    for(int i=i;i<N;++i){
        if (i==1)dp[i]=abs(h[i]-h[i-1]);
        else dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
    }
    cout<<dp[N-1]<<endl;    
}