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]で、最後の入力値を出力します.