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

こんばんわ、syachiです。

さっそくですが、

今日は月曜日ということで、AtCoder関連のお勉強ですね。

私の実力は本当にザコーダーなので、レベルアップのために動的計画法なるものを学ぶことにします。

動的計画法について、参考にしているのは以下の記事

 https://qiita.com/drken/items/dc53c683d6de8aeacf5a

ここにある通り、

動的計画法にはいくつかのパターンがあり、

それを学ぶことで応用が効くということらしい。

今日は本当に初歩の初歩で、最初の問題。

問題はこちら

https://atcoder.jp/contests/dp/tasks/dp_a

そして、私の解はこちら

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):
    dp.append(100000000000000)

for i in range(N):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(a[1] - a[0])
    else:
        dp[i] = minVal(dp[i], dp[i - 1] + abs(a[i - 1] - a[i]))
        dp[i] = minVal(dp[i], dp[i - 2] + abs(a[i - 2] - a[i]))

print(dp[N - 1])

ほとんど真似て作ったので、色がないですね…。

これをサクッと頭で考えられるようになるには、日々の鍛錬しかなさそうです。

〜追記〜

これを書いてたら以下の内容も書きたくなったのでそのうち

・私のiPhoneでのAtCoderのやり方

・使用言語について

プログラムの表記を見やすくしました。

ついでに、ちょっとプログラムを改変してみます。

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

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

dp = [100000000000000] * N
(dp[0], dp[1]) = [0, abs(a[1]-a[0])]

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

なかなかシンプルになった？

初期化部分とか、for, else部分がポイントでしょうか。

ちなみにminValは自分で作ってますが、pythonには組み込み関数min()があります。

こちらを使うとコードはさらに減ります。

・・・その代わり実行時間は伸びました、興味深いです。