動的計画法（部屋移動）

問題

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

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

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

🔹部屋 i−1 から部屋 i に向かう通路を通るのに Ai 分 (2≦i≦N) かかる
🔹部屋 i−2 から部屋 i に向かう通路を通るのに Bi 分 (3≦i≦N) かかる

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

[制約]
🔹3≦n≦100000
🔹1≦Ai≦100　(2≦i≦N)
🔹1≦Bi≦100　(3≦i≦N)

解き方・ソースコード

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

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

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

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

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

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

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

dp[i]=min(dp[i−1]+Ai,dp[i−2]+Bi)

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

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分であることを導き出すことができました😊