DP問題を解いてみた

注意

初心者なので、至らない点が多々あると思います。
先にお詫び申し上げます。

問題

A - Frog 1
$N$個の足場があります。足場には$1,2,\ldots,N$と番号が振られています。
各$i(1 \leq i \leq N)$について、足場$i$の高さは$h_i$です。
最初、足場$1$にカエルがいます。カエルは次の行動を何回か繰り返し、足場$N$まで辿り着こうとしています。
・足場$i$にいるとき、足場$i+1$または足場$i+2$へジャンプする。このとき、ジャンプ先の足場を$j$とすると、コスト$\left| h_i-h_j \right|$を支払う。
カエルが足場$N$に辿り着くまでに支払うコストの最小値を求めてください。

解法

方針

DPコンテストなので、DPを使うために漸化式を作る。

やってみる

足場$i$に辿り着くまでに支払うコストの最小値を$c_i$とおく。
$c_1=0$は自明。
足場$i$に辿り着くまでに、足場$i-1$か足場$i-2$またはその両方を必ず経由する。

足場$i$に辿り着くまでに支払うコスト

• 足場$i-1$のみを経由する場合
  $c_{i-1}+\left| h_{i-1}-h_i \right|$
• 足場$i-2$のみを経由する場合
  $c_{i-2}+\left| h_{i-2}-h_i \right|$
• 足場$i-1$と足場$i-2$の両方を経由する場合
  $c_{i-2}+\left| h_{i-2}-h_{i-1} \right|+\left| h_{i-1}-h_i \right|$

ここで$c$の定義より、
$c_{i-1} \leq c_{i-2}+\left| h_{i-2}-h_{i-1} \right|$
よって、
$c_{i-1}+\left| h_{i-1}-h_i \right| \leq c_{i-2}+\left| h_{i-2}-h_{i-1} \right|+\left| h_{i-1}-h_i \right|$
これらの場合における最小値が$c_i$だから、
$\begin{align} c_i&=\min(c_{i-1}+\left| h_{i-1}-h_i \right|,c_{i-2}+\left| h_{i-2}-h_i \right|,c_{i-2}+\left| h_{i-2}-h_{i-1} \right|+\left| h_{i-1}-h_i \right|)\\ &=\min(c_{i-1}+\left| h_{i-1}-h_i \right|,c_{i-2}+\left| h_{i-2}-h_i \right|) \end{align}$
以上をまとめると、
$\begin{eqnarray} \left\{ \begin{array}{l} c_1=0 \\ c_i=\min(c_{i-1}+\left| h_{i-1}-h_i \right|,c_{i-2}+\left| h_{i-2}-h_i \right|) \end{array} \right. \end{eqnarray}$
となる。
あとはプログラムを書けば解くことができ、この漸化式を解くオーダーは$O(N)$である。

感想・まとめ

今まで直感でDP問題を解いてきましたが、初めて漸化式によって解けて嬉しいです。
これでAtcoderでのスキルを上げれると自分に期待しています。