Algorithm|[規格2579]階段を上る(DP,Python)

[白俊2579]登上阶段

ダイナミックプログラミング

質問する

階段を登るゲームは、階段の下の起点から階段の先端にある到達点までのゲームです.
階段を登るには以下のルールがあります.
階段は一度に1段または2段上がることができます.つまり、階段に沿って、次の階段を上ったり、次の階段を下りたりすることができます.
連続した3つの階段を踏んではいけない.しかし、起点は階段には含まれていません.
最後に着いた階段は必ず踏まなければなりません.
そのため、最初の階段に沿って、2番目か3番目の階段を歩くことができます.しかし、最初の階段を踏んで4番目の階段を登ったり、最初の階段、2番目の階段、3番目の階段を連続して踏んだりすることはできません.
各段階の点数を与える場合は、ゲームの総点数の最値を求めるプログラムを作成します.

入力

入力した最初の行には、階段の数が表示されます.
2行目から、1行1つ、一番下の階段から、各階段に書いてある点数を順番にあげます.階段の個数は300以下の自然数で、階段に書いてある点数は10000以下の自然数です.

しゅつりょく

1行目に階段を登るゲームで得られる総得点の最値を出力します.

入力例

6
10
20
15
25
10
20

サンプル出力

75

問題を解く

基本的なDP問題ですが、点火式を見つけるのに時間がかかりました.重要なのは、前の階段から上がる場合と、2番目の前の階段から上がる場合に分けて考えることです.どちらの場合も大きな値をとり,直接階段の1〜3格子を求め,4格子目から点火式により値を求めた.
1π
2𗜋▁𗜋2つの格の前から上がってきた点火式:stair[i]+d[i-2]

import sys
input = sys.stdin.readline

num = int(input())
stair = [0 for _ in range(num+3)]
d = [0 for _ in range(num+3)]

for i in range(1, num+1):
    stair[i] = int(input())

d[1] = stair[1]
d[2] = stair[2]+stair[1]
d[3] = max(stair[3]+stair[2],stair[3]+d[1])

for i in range(4, num+1):
    d[i] = max(stair[i]+stair[i-1]+d[i-3],stair[i]+d[i-2])

print(d[num])

📌入力部のsysを受信します.stdin.readlineを使用しないとタイムアウトが発生します.