[DP/白駿]2579


白駿2579号問題
def solution(n, stair_array):

    count_array = [0 for _ in range(n)]

    if n == 1:
        return stair_array[0]
    
    if n == 2:
        return stair_array[0] + stair_array[1]

    count_array[0] = stair_array[0]
    count_array[1] = stair_array[0] + stair_array[1]
    count_array[2] = max((stair_array[0] + stair_array[2]), (stair_array[1] + stair_array[2]))

    for i, _ in enumerate(count_array):
        if i == 0 or i==1 or i==2:
            continue
        count_array[i] = max((count_array[i-3] + stair_array[i-1] + stair_array[i]), (count_array[i-2] + stair_array[i]))
    
    return count_array[n-1]

n = int(input())
stair_array = []

for i in range(n):
    stair_array.append(int(input()))

print(solution(n, stair_array))
  • nは自然数であり、n=1、n=2の場合のみ例外処理(例外処理をしないとoutofindex男)
  • が行われている.
  • 今の階段の最高価格は
    (3番目の前のレベルの最上位+前のレベルの値)
    vs
    (第2段階までの最低価格)
    で選択する
  • このようにしてこそ、2回の登り限界(まず無条件2回の登りを比較する)
  • を防止することができる.

    実は4点ですが、リズムの変化によって変わるレベルなので、別に書いていません.