1. 题目
2. 分析
这道题比较简单。从这道简单的题来看,动态规划做的事儿就是:
- 设定一个状态,这个状态可以需要用一个数组来记录
- 确定状态间的转移公式
得出正确解
3. 代码
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
cost.append(0) # 最后添加一个台阶,标识楼梯顶部
dp = [0] * len(cost) # dp[i] 表示到第i个台阶的最小成本
for i in range(2,len(cost)):
# 第i个台阶,只有两种上法:分别是从第i-1个台阶和第i-2个台阶上来
# 这就是我们需要的转移方程
dp[i] = min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1])
return dp[-1]