動的計画法(ウサギの足場/ルート復元)

問題

$ N $ 個の足場があり、左から $ i $ 番目の足場(足場 $ i $ とする)の高さは $ h_i $ です。

ウサギは以下の2種類の行動を繰り返すことで、足場1から足場 $ N $ に移動します。

 🔹足場 $ i - 2 $ から足場 $ i $ に、コスト $ | h_{i-2} - h_i | $ かけて移動する。
 🔹足場 $ i - 1 $ から足場 $ i $ に、コスト $ | h_{i-1} - h_i | $ かけて移動する。

足場 $ 1 $ から足場 $ N $ に移動するのに、最短コストのルートを1つ出力して下さい。

解き方・ソースコード

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

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

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

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

 🔹$ dp[x] = dp[x - 1] + | H[x - 1] - H[x] | $ の場合:方法Aを選ぶ
 🔹$ dp[x] = dp[x - 2] + | H[x - 2] - H[x] | $ の場合:方法Bを選ぶ

なお、上の2つの条件両方を満たす場合は、方法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
31
32
33
34
35
36
#--------- 入力例 ----------
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)

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

# どこから足場 Place に向かうのが最適かを求める
if dp[Place - 1] + abs(H[Place - 1] - H[Place]) == dp[Place]:
Place = Place - 1 # 1つ前の足場に移動
else:
Place = Place - 2 # 2つ前の足場足場に移動

# 答えを出力(Answer[0]が足場1に対応)
print('解:', ' → '.join(str(i + 1) for i in reversed(Answer)))

[実行結果]

[5]

[5, 4]

[5, 4, 2]

[5, 4, 2, 0]

解: 1 → 3 → 5 → 6

最短コストにするためには1 → 3 → 5 → 6というルート(経路)であることが確認できました😊