题解 | #最小花费爬楼梯#
最小花费爬楼梯
https://www.nowcoder.com/practice/6fe0302a058a4e4a834ee44af88435c7
class Solution:
def minCostClimbingStairs(self , cost: List[int]) -> int:
dp = [0 for i in range(len(cost)+1)]
for i in range(2, len(cost)+1):
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
return dp[-1]
解题思路
- 先构建一个长度为cost长度+1的数组（0-n）；
- 循环计算到每一个阶梯最小的花费是什么，得到转移状态方程，即dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])。
复杂度
时间复杂度为O（N），空间复杂度为O（N）。
