0%

AP325 P-6-1 小朋友上樓梯最小成本 (d066)

第一次自己寫DP

題解

先把圖畫出來
接下來想到 dp[i] 會是第i階樓梯的最小花費
列一下轉移方程式
找說要算出這一階要怎麼算
dp[i] = min(dp[i-2] + stair[i], dp[i-1] + stair[i])
我的想法是 前一階+這一階 和 前面兩階+這一階 去找最小的(因為題目說以走一階或兩階)

Code

import sys

N = int(sys.stdin.readline().strip())
dp = [0 for x in range(N+5)]

all = list(map(int, sys.stdin.readline().strip().split(' ')))
# print(all)

dp[0] = 0

for i in range(N):
    dp[i+1] = min(dp[i-1] + all[i], dp[i] + all[i])

print(dp[N])