動的計画法（ルート復元）

問題

$ 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) $

解き方・ソースコード

前々回の記事では同じ問題の最短時間を求めましたが、今回は最短時間で移動する際のルート（経路）を求める問題となります。

この問題ではゴールから順番にスタートへの経路を考えることで解くことができます。

まずは、前々回記事と同様に動的計画法を使って最短時間を求めます。

この時に作成した $ dp $ を確認すると次のように最適解(最短時間となるルート)を求めることができます。

　🔹$ dp[x] = dp[x-1] + A_x $ の場合：方法Aを選ぶ
　🔹$ dp[x] = dp[x-2] + B_x $ の場合：方法Bを選ぶ

なお、上の２つの条件両方を満たす場合は、方法A・方法Bどちらを選んでも構いません。

最後に、復元した経路を逆順に並べ替えることにより、最短ルートを求めます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#--------- 入力例 ----------
N = 5
A = [2, 4, 1, 3]
B = [5, 3, 7]
#---------------------------
# 動的計画法
dp = [None] * (N + 1)
dp[1] = 0
dp[2] = A[0]
for i in range(3, N + 1):
    dp[i] = min(dp[i - 1] + A[i - 2], dp[i - 2] + B[i - 3])

# 答えの復元
# 変数 Place は現在位置（ゴールからスタート地点へ向かう）
Answer = []
Place = N
while True:
    Answer.append(Place)
    print(Answer)
    if Place == 1:
        break

    # どこから部屋 Place に向かうのが最適かを求める
    if dp[Place - 1] + A[Place - 2] == dp[Place]:
        Place = Place - 1   # １つ前の部屋に移動
    else:
        Place = Place - 2   # ２つ前の部屋に移動

# 答えを出力
print('解：', ' → '.join(str(i) for i in reversed(Answer)))

[実行結果(入力例1)]

[5]

[5, 4]

[5, 4, 2]

[5, 4, 2, 1]

解： 1 → 2 → 4 → 5

最短時間にするためには1 → 2 → 4 → 5という経路であることが確認できました😊