2579号:階段を上る
import sys
input = sys.stdin.readline
n = int(input())
li = [int(input()) for _ in range(n)]
dp = []
if n == 1:
print(li[0])
elif n == 2:
print(li[0]+li[1])
elif n == 3:
print(max(li[0]+li[2],li[1]+li[2]))
else:
dp.append(li[0])
dp.append(li[0]+li[1])
dp.append(max(li[0]+li[2], li[1]+li[2]))
for i in range(3,n):
dp.append(max(li[i] + li[i-1] + dp[i-3], li[i] + dp[i-2]))
print(dp[-1])
受信するスコアのリストliと、最小スコアを保存するリストdpを作成します.n ifゲートを利用すると
1の場合、li[0]が出力されます.
2の場合、li[0]+li[1]またはsum(li)が出力されます.
3の場合、max(li[0]+li[2],li[1]+li[2])が出力されます.
nは1、2、3以外の数字です.
1、2、3日前の最小スコアをdpリストに保存します.
dpのインデックス0,1,2は3からn−1に埋め込まれている.
このとき、最も高価な充填方法は階段を登るときに最後の1つをずっと踏んでいることです.
li[i-3]の最大値dp[i-3]とli[i-2]をスキップし、li[i-1]を介してli[i]に足を踏み入れる方法
li[i-2]の最大値dp[i-2]とli[i-1]にスキップし、li[i]を踏む方法で最大値を保存します.
出力はdp[-1]で、最後の入力値を出力します.
Reference
この問題について(2579号:階段を上る), 我々は、より多くの情報をここで見つけました https://velog.io/@mae03087/2579번-계단-오르기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol