pythonでコーディング問題を解く5

https://qiita.com/tosei/items/58e56b9c7dd587468f34
続き

動的計画法で気になった問題を解いてみた

問題1

A Frog1

import numpy

count = int(input())
# スペースで区切ってint型のmapにする
# mapの戻り値は配列ではないので、listで配列に変換する
heights = list(map(int, input().split(' ')))
dp = list(numpy.full(count, 0))

# 一番最初の隣の柱に移動した時点では、必ず|2番目 - 1番目|がスコアになる
dp[1] = abs(heights[1] - heights[0])

# 2番目以降は、一つ前から移動した場合と、二つ前から移動した場合のスコアを比較し、小さいほうを設定するのを最後まで繰り返す
for cur in range(2, len(dp)) :
    dp[cur] = min(dp[cur - 1] + abs(heights[cur] - heights[cur - 1]), dp[cur - 2] + abs(heights[cur] - heights[cur - 2]))
    
print(dp)

問題2

B Frog2

import numpy

count, maxStep = map(int, input().split(' '))
heights = list(map(int, input().split(' ')))
dp = list(numpy.full(count, 0))

dp[1] = abs(heights[1] - heights[0])

for cur in range(2, count) :
    # 一段前から上ったときの合計値をdpにセットする
    dp[cur] = dp[cur - 1] + abs(heights[cur] - heights[cur - 1])
    
    # 2段以上前から登った時の合計値をdp[cur]と比較し、小さいほうで更新する
    # rangeは(x, y)としたとき、x<=val<yなので、maxStep+1とする
    for step in range(2, maxStep + 1) :
        # maxStepが現在地点よりも大きい場合、マイナスになりアクセス違反が起きるのを防ぐため
        if cur - step >= 0:
            dp[cur] = min(abs(heights[cur] - heights[cur - step]) + dp[cur - step], dp[cur])
    
print(dp)