DP4 题解 | #最小花费爬楼梯#

#动态规划五部曲——确定dp数组含义、写出递推公式、初始化、遍历、打印数组（debug）

#确定dp数组含义
#dp[i]表示到达第i个台阶的最小花费

#写出递推公式
#dp[i]=min(dp[i-1]+cast[i-1],dp[i-2]+cast[i-2])

#初始化
#dp[0]=0,dp[1]=0 这里有点坑，可能会以为dp[1]=cast[0],实际上题目说了可以从0或者1出发，所以dp[1]也是0

n=int(input())
cast=[int(i) for i in input().split()]
# print(cast)
dp=[0 for i in range(n+1)]
dp[0]=0
dp[1]=0
for i in range(2,n+1):
    dp[i]=min(dp[i-1]+cast[i-1],dp[i-2]+cast[i-2])
# print(dp)
print(dp[-1])