問題
$ N $ 個の足場があり、左から $ i $ 番目の足場（足場 $ i $ とする）の高さは $ h_i $ です。
ウサギは以下の２種類の行動を繰り返すことで、足場１から足場 $ N $ に移動します。
🔹足場 $ i - 2 $ から足場 $ i $ に、コスト $ | h_{i-2} - h_i | $ かけて移動する。
🔹足場 $ i - 1 $ から足場 $ i $ に、コスト $ | h_{i-1} - h_i | $ かけて移動する。
移動にかかる合計コストの最小値を出力して下さい。
解き方・ソースコード
この問題は、足場１から足場 $ i $ までの最小コストを $ dp[i-1] $ とし、$ dp[0] → dp[1] → ･･･ → dp[N-1] $ の順に１つずつ計算すると、答えを出すことができます。
配列 $ dp $ の計算方法としては、まず足場１から足場１までは移動する必要がないので、$ dp[0] = 0 $ となります。
次に足場１から足場２まで行くには直接移動するしかないので、$ dp[1] = h_0 - h_1 $ となります。
$ dp[2] $ 以降は最後の行動で場合分けをして考えます。足場 $ i $ まで移動するには、次の２つが考えられます。
（方法１）足場 $ i - 1 $ まで移動した後、１つ隣りの足場 $ i $ に行く。
（方法２）足場 $ i - 2 $ まで移動した後、２つ隣りの足場 $ i $ に行く。
ここで、方法１を選んだ時の合計コストは $ dp[i - 1] + abs(H[i - 1] - H[i]) $ であり、方法２を選んだ時の合計コストは $ dp[i - 2] + abs(H[i - 2] - H[i]) $ です。
コストの少ないほうを求める問題なので、$ dp[i] $ の値は次式のように表すことができます。
$$ dp[i] = min(dp[i-1] + abs(H[i - 1] - H[i]), dp[i-2] + abs(H[i - 2] - H[i])) $$
上記の内容を踏まえてコーディングすると下記のようなソースコードになります。
[Google Colaboratory]
1 | #--------- 入力例 ---------- |
[実行結果(入力例1)]
足場1までの最小コスト [0, None, None, None, None, None] 足場2までの最小コスト [0, 20, None, None, None, None] 足場3までの最小コスト [0, 20, 30, None, None, None] 足場4までの最小コスト [0, 20, 30, 20, None, None] 足場5までの最小コスト [0, 20, 30, 20, 30, None] 足場6までの最小コスト [0, 20, 30, 20, 30, 40] 解： 40
足場１→足場３→足場５→足場６と移動すると最小コスト40で移動することができます。
