1. Problem 📃

📚 ソース-2579-階段を登る
問題の説明
階段を登るゲームは階段の下の起点から階段の先端の終点までのゲームです.図1>に示すように、階段ごとに一定の点数が書かれており、階段を踏むと階段の点数が得られます.

<図2>に示すように、始点から、第1、2、4、6段の階段を歩いて終点に着き、合計10+20+25+20=75点となる.

階段を登るには以下のルールがあります.

級は1回に1級または2級に上がることができる.つまり、階段に沿って、次の階段を上ったり、次の階段を下りたりすることができます.

3つの連続した階段は、

も踏んではいけません.しかし、起点は階段には含まれていません.

最後に到着した階段は踏まなければなりません.

そのため、最初の階段に沿って、2番目か3番目の階段を歩くことができます.しかし、最初の階段を踏んで4番目の階段を登ったり、最初の階段、2番目の階段、3番目の階段を連続して踏んだりすることはできません.
各段階の点数を与える場合は、ゲームの総点数の最値を求めるプログラムを作成します.
入力
入力した最初の行には、階段の数が表示されます.
2行目から、1行1つ、一番下の階段から、各階段に書いてある点数を順番にあげます.階段の個数は300以下の自然数で、階段に書いてある点数は10000以下の自然数です.
しゅつりょく
1行目に階段を登るゲームで得られる総得点の最値を出力します.
I/O例
サンプル入力サンプル出力61002051525102075

2. Logic 👨‍🏫

この問題はDP(ダイナミックプランニング法)により,すべての方法を一つ一つチェックし,最適解のアルゴリズムを探し出して解決する問題である.逆に、グリディアルゴリズム(貪欲アルゴリズム)は、その瞬間の最適解を探す方法である.この問題は私にはちょっと難しいので、まず見てみましょう.
Logic
この問題をそのまま解釈することは可能だが、逆に考えることもできる.
最終段階の立場から、규칙3を満たすとともに、규칙 1, 2も適用される.
2つのケースがあり、まず最後のステップ(n)を基準としてn-1, n-3、次に最後のステップ(n)を基準としてn-2を踏む.
この点を理解するのは簡単ですが、この考えを達成するには少し難しいです.問題がまだ終わっていないのでもっとやらなければならないようです.

3. Code 💻

1.参照解読コード😁

def cal():
    if N == 1:
        return stair[0]
    elif N == 2:
        return (stair[0] + stair[1])
    else:
        dp = [0] * N
        dp[0] = stair[0]
        dp[1] = stair[0] + stair[1]
        dp[2] = max(stair[0] + stair[2], stair[1] + stair[2])

        for i in range(3, N):
            dp[i] = max(stair[i] + stair[i-1] + dp[i-3], stair[i] + dp[i-2])
    
    return dp[-1]

N = int(input())
stair = [int(input()) for _ in range(N)]
print(cal())

参考資料📩
白駿2579参考記事