题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是从第 0 或 1 开始爬楼梯，每个楼梯有花费，求爬到楼顶的最小花费。

思路分享

  • 划分子问题，本题可以把爬到第 n 阶的最小花费变成爬到第 n-1 阶的最小花费问题，搞定这个就能写出来回溯dfs。然后再转递推。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        f = [0] * (n+1)
        f[0] = cost[0]
        f[1] = cost[1]
        for i in range(2, n):
            f[i] = min(f[i-1], f[i-2]) + cost[i]
        
        return min(f[n-1], f[n-2])

        # @cache
        # def dfs(i :int) -> int:
        #     if i == 0 or i == 1:
        #         return cost[i]
        #     return min(dfs(i-1), dfs(i-2)) + cost[i]
        
        # return min(dfs(n-1), dfs(n-2))