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

これを最小コストの配列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;
}