動的計画法（ウサギの足場）

問題

$ 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#--------- 入力例 ----------
N = 6
H = [30, 10, 60, 10, 60, 50]
#---------------------------
# 配列の準備
dp = [ None ] * N

# 動的計画法
dp[0] = 0
print('足場1までの最小コスト', dp)

dp[1] = abs(H[0] - H[1])
print('足場2までの最小コスト', dp)

for i in range(2, N):   # 足場3以降の最小コスト
    dp[i] = min(dp[i - 1] + abs(H[i - 1] - H[i]), dp[i - 2] + abs(H[i - 2] - H[i]))
    print('足場{}までの最小コスト'.format(i + 1), dp)

# 出力
print('解：', dp[N - 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で移動することができます。