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

動的計画法

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

[問題]

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

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

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

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

足場 i にいるとき、足場 i + 1, i + 2, …, i + K のどれかへジャンプする。 

このとき、ジャンプ先の足場を j とすると、コスト ∣h_i − h_j∣ (差分の絶対値)を

コストとして支払う必要があります。

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

解法・ソースコード

前回の問題との違いは、ジャンプする幅が i+1, i+2 だけではなく、i + K と可変になっているところです。

ただし、前回の処理で +1, +2 の２パターンで処理していた個所を、K回ループで回す 処理に変えるだけなので、ほんの少しの修正で対応することが可能です。

修正したソースコードは次のようになります。

[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
#--------- 入力例1 ----------
k=3
lst = [10, 30, 40, 50, 20]
#--------- 入力例2 ----------
# k=1
# lst = [10, 20, 10]
#--------- 入力例4 ----------
# k=100
# lst = [10, 10]
#--------- 入力例4 ----------
# k=4
# lst = [40, 10, 20, 70, 80, 10, 20, 70, 80, 60]
#----------------------------
n = len(lst)      # 段差の数

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

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

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

30

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

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

20

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

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

0

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

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

40

足場 1 → 4 → 8 → 10 と移動すると、コストの総和は ∣ 40 − 70 ∣ + ∣ 70 − 70 ∣ + ∣ 70 − 60 ∣ = 40 となります。