【月曜日】動的計画法について学ぶ②

こんばんわ、syachiです。

今日って一応平日なんですね…。

ということで月曜なので、AtCoderの問題、

動的計画法の学習の続きです。

前回は簡単な問題で解法を試しましたが、

実はもう一通りの解き方があるらしく。

コストの最小値を見える化してリスト化した際、

前回はある一点にたどり着くまでのコストを計算してましたが、

今回は逆に、ある一点からたどり着ける場所のコストを計算する、ということだそうです。

実装例はこちら。

N = int(input())
a = list(map(int, input().split()))


def minVal(minInt, val):
    if minInt < val:
        return minInt
    else:
        return val


dp = []

for i in range(N + 5):
    dp.append(100000000000000)
dp[0] = 0

for i in range(N):
    if (i + 1) < N:
        dp[i + 1] = minVal(dp[i + 1], dp[i] + abs(a[i + 1] - a[i]))
    if (i + 2) < N:
        dp[i + 2] = minVal(dp[i + 2], dp[i] + abs(a[i + 2] - a[i]))
# print(dp)
print(dp[N - 1])

最初の部分のifを書かなくて良い分、

こちらの方が好きかも…。

色々最適化の余地を残しつつ、

時間がないのでこのへんで。