2579番の階段を上る

5067 ワード
どうてきけいかくほう boj テキストリンク
質問元:https://www.acmicpc.net/problem/2579
DPアルゴリズムを用いて初めて解いた問題.今ではDPがよく使われていますが、最初に思いついたのはDPです.

思考過程.


あなたが以前どう思っていたのか分かりません.今なら、条件に従って問題を解剖し、問題を整理します.
1.次または次のセル
2.連続する3つのX、つまり、1つの格子を踏むと、必ず1つの格子を踏む.
3.最後に着いた階段は必ず踏んでください.最後の格子を基準に考えてみましょう逆さまに!
最後のセル(N)は、(N−1)または(N−2)からまとめられる.条件のため、N-1から来ると条件が付きます…(N-3段階段を踏んでくる)
では、Nは、「N-1段階段を踏んだとき」と「N-2段階段を踏んだとき」の中で、より大きなものを踏んでいるのではないでしょうか.階段の値に加えて、1段目階段を踏んだときに得られる最高価格は、もう1つのリストmemorizationです.これがDPの特徴です.
*最終的には、答えの構造、式のみにまとめることができます.
import sys

N = int(sys.stdin.readline().rstrip("\n"))
stair=[0]+[int(sys.stdin.readline().rstrip("\n")) for _ in range(N)]
dp = [0 for _ in range(N+1)]
for n in range(1,3) :
    dp[n]=stair[n]+stair[n-1]
    if N==1 : break

for i in range(3,N+1) :
    dp[i]=max(dp[i-3]+stair[i-1],dp[i-2])+stair[i]
print(dp[N])
もっと鋭くやりたいのが限界なのか...
dom-to-imageを試す
amd-gpu in ubuntu