動的計画法（部屋移動）

問題

$ N $ 個の部屋があり、$ 1 $ から $ N $ までの番号が付けられています。

この部屋はすべて一方通行であり、通路を介して１つ先または２つ先の部屋に移動できます。

各通路における移動時間は以下の通りです。

🔹部屋 $ i - 1 $ から部屋 $ i $ に向かう通路を通るのに $ A_i $ 分 $ (2 \leqq i \leqq N) $ かかる
🔹部屋 $ i - 2 $ から部屋 $ i $ に向かう通路を通るのに $ B_i $ 分 $ (3 \leqq i \leqq N) $ かかる

部屋 $ 1 $ から部屋 $ N $ に移動するのに、最短何分かかるでしょうか。

[制約]
🔹$ 3 \leqq n \leqq 100000 $
🔹$ 1 \leqq A_i \leqq 100　 (2 \leqq i \leqq N) $
🔹$ 1 \leqq B_i \leqq 100　 (3 \leqq i \leqq N) $

解き方・ソースコード

この問題は、部屋１から部屋 $ i $ までの最短時間を $ dp[i] $ とし、$ dp[1] → dp[2] → ･･･ → dp[N] $ の順に１つずつ計算すると、答えを出すことができます。

配列 $ dp $ の計算方法としては、まず部屋１から部屋１までは移動する必要がないので、$ dp[1] = 0 $ となります。

次に部屋１から部屋２まで行くには直接移動するしかないので、$ dp[2] = A_2 $ となります。

$ dp[3] $ 以降は最後の行動で場合分けをして考えます。部屋 $ i $ まで移動するには、次の２つが考えられます。

　（方法１）部屋 $ i - 1 $ まで移動した後、１本の通路を通って部屋 $ i $ に行く。
　（方法２）部屋 $ i - 2 $ まで移動した後、１本の通路を通って部屋 $ i $ に行く。

ここで、方法１を選んだ時の合計時間は $ dp[i - 1] $ 分であり、方法２を選んだ時の合計時間は $ dp[i - 2] $ 分です。

時間の短いほうを求める問題なので、$ dp[i] $ の値は次式のように表すことができます。

$$ dp[i] = min(dp[i-1] + A_i, dp[i-2] + B_i) $$

上記の内容を踏まえてコーディングすると下記のようなソースコードになります。

A, B が 0 番目から始まっていることに注意して下さい。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#--------- 入力例 ----------
N = 5
A = [2, 4, 1, 3]
B = [5, 3, 7]
#---------------------------
# 動的計画法
dp = [ None ] * (N + 1)

dp[1] = 0       # 部屋1までの最短時間
print('部屋1番目までの最短時間', dp)

dp[2] = A[0]    # 部屋2までの最短時間
print('部屋2番目までの最短時間', dp)

for i in range(3, N + 1):
    dp[i] = min(dp[i - 1] + A[i - 2], dp[i - 2] + B[i - 3])
    print('部屋{}番目までの最短時間'.format(i), dp)
# 出力
print('解：', dp[N])

[実行結果]

部屋1番目までの最短時間 [None, 0, None, None, None, None]

部屋2番目までの最短時間 [None, 0, 2, None, None, None]

部屋3番目までの最短時間 [None, 0, 2, 5, None, None]

部屋4番目までの最短時間 [None, 0, 2, 5, 5, None]

部屋5番目までの最短時間 [None, 0, 2, 5, 5, 8]

解： 8

部屋1から部屋5までの最短時間が8分であることを導き出すことができました😊