アルゴリズム勉強

内容・目的

　テキストの5章1問目に関して理解を深めるとともに文章能力，言語能力を向上させるためにoutputとしてこの記事を作成した.
AtCoderの緑レート目指して頑張る．

内容・概要

問題
この問題を読んだ時に考えた解法はforg問題の発展形のように予測し，frog問題の解法を元に制約をつけ加えた問題として仮定した.
問題の制約としてネックだったのは，同じ選択(a,b,c)を選んではならないという点だった. そのことから３日間の合計が最大となるように取ればよいのではないかと予測し，解を求めようとして失敗した.

その後回答のコード(c++)をGminiでpythonに変換させコードの解読と解釈をしたものを下記に示す.

def solve(N, a):
    dp = [[0] * 3 for _ in range(N + 1)]

    for i in range(N):
        for j in range(3):
            for k in range(3):
                if j != k:
                    dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + a[i][k])

    return max(dp[N])
# 解く
ans = solve(N, a)
print(ans)

このコードがやっていることはdpテーブルを作製するとき，各dpテーブルの仮にi番目でのa,b,cでの最大値を取るようにしている．そのようにすることでi+2の時にa,b,cのどれでも結果的に最大を求めることが出来るからだ．

参考・引用

問題AtCoder
アルゴリズムとデータ構造