カエルの段差移動（動的計画法④）

動的計画法

カエルが最小コストで段差を移動する問題を、動的計画法 を使って解いていきます。

[問題]

Ｎ個の足場があります。 足場には 1,2,…,N と番号が振られています。

各 i (1 ≦ i ≦  N) について、足場 i の高さは h_i です。

最初にカエルは、足場 1 にいます。

カエルは次の行動を何回か繰り返し、足場Nまで辿り着こうとしています。

足場 i にいるとき、足場 i + 1 または i + 2 へジャンプします。

このとき、ジャンプ先の足場を j とすると、コスト ∣h_i − h_j∣ (差分の絶対値)を支払う必要があります。

カエルが足場 N に辿り着くまでに支払うコストの 総和の最小値 を求めてください。

解法・ソースコード

メモ化テーブル memo[i] を頂点iへと至る最短経路を表していると定義します。

memo[i] の値を求めるために、次の２つを比較します。

  • 頂点 i - 1まで最短経路で行ってから、頂点 i へと至る方法の最小コスト
    memo[i - 1] + abs(h[i] - h[i - 1])
  • 頂点 i - 2まで最短経路で行ってから、頂点 i へと至る方法の最小コスト
    memo[i - 2] + abs(h[i] - h[i - 2])

memo[i] の値は、これらのうちの 最小値 となります。

以上を踏まえて実装すると以下のようなソースになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#--------- 入力例1 ----------
lst = [10, 30, 40, 20]
#--------- 入力例2 ----------
# lst = [10, 10]
#--------- 入力例3 ----------
# lst = [30, 10, 60, 10, 60, 50]
#----------------------------
n = len(lst)    # 足場の数

memo = [float('inf')] * n
memo[0] = 0

for i in range(n):
    if i - 1 >= 0:
        memo[i] = min(memo[i], memo[i - 1] + abs(lst[i] - lst[i - 1]))
    if i - 2 >= 0:
        memo[i] = min(memo[i], memo[i - 2] + abs(lst[i] - lst[i - 2]))
print(memo[n - 1])

[実行結果（入力例1）]

30

足場 1 → 2 → 4 と移動すると、コストの総和は ∣10 − 30∣ + ∣30 − 20∣ = 30 となります。

[実行結果（入力例2）]

0

足場 1 → 2 と移動すると、コストの総和は ∣ 10 − 10 ∣ = 0 となります。

[実行結果（入力例3）]

40

足場 1 → 3 → 5 → 6 と移動すると、コストの総和は ∣ 30 − 60 ∣ + ∣60 − 60 ∣ + ∣ 60 − 50 ∣ = 40 となります。