题目浅析

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

  • 简单地说，就是给一个 n 阶台阶，规定从第 i 级台阶跳到第 j 级台阶的成本定义为： costs[j] + (j - i)^2，求从 0 到台阶顶的最小成本。

思路分享

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

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def climbStairs(self, n: int, costs: List[int]) -> int:
        n = len(costs)

        f = [0] * (n+1)
        f[0] = 0
        for i in range(1, n+1):
            f[i] = min(f[j] + (j-i)*(j-i) for j in range(max(i-3, 0), i))+costs[i-1]
        # print(f)
        return f[n]
        
        # 记忆化回溯
        # @cache
        # def dfs(i:int)-> int:
        #     if i == -1:
        #         return 0
        #     res = inf
        #     for j in range(i-1, i-4, -1):
        #         if j < -1:
        #             break
        #         res = min(res, dfs(j)+costs[i] + (j-i)*(j-i))
        #     # print(str(i) + ":" + str(res))
        #     return res
        
        # return dfs(n-1)