能否用Python的@cache实现递归式自底向上动态规划？

问题描述 #

给定整数数组cost，cost[i]是第i级台阶的花费，支付费用后可爬1或2级台阶，可从索引0或1开始，求到达顶部的最小花费。

已实现的自顶向下记忆化解法（@cache版） #

我用Python的@cache装饰器实现了自顶向下动态规划的记忆化解法，代码简洁直观：

from functools import cache

class Solution:
        
    def minCostClimbingStairs(self, cost) -> int:

        @cache
        def minCostAux(curStep):
                       
            if curStep == -1: return 0 
            if curStep == 0: return cost[0]
            return min(minCostAux(curStep-2) + cost[curStep], minCostAux(curStep-1) + cost[curStep]) 

        cost.append(0)
        return minCostAux(len(cost)-1)

手动缓存的自底向上递归解法 #

不用@cache的递归自底向上解法如下，需要显式维护缓存数组：

class Solution:    
            
    def minCostClimbingStairs(self, cost) -> int:

        def minCostAux(step_i):
            # 返回已缓存的结果
            if minCosts[step_i] != -1:
                return minCosts[step_i]
                
            # 缓存当前台阶的最小花费
            minCosts[step_i] = min(minCostAux(step_i-1 )
                                 , minCostAux(step_i-2)) + cost[step_i]

            # 到达最后一步时返回最终结果
            if step_i == len(cost)-1: return minCosts[step_i]

            # 递归计算下一个台阶
            return minCostAux(step_i+1)

        cost.append(0) # 添加顶部虚拟台阶，统一计算逻辑

        # 初始化缓存数组
        minCosts = [-1] * len(cost)

        # 缓存基础情况
        minCosts[0] = cost[0]
        minCosts[1] = min(cost[0]+cost[1], cost[1])
        
        # 从第2级开始递归计算
        return minCostAux(2)

疑问：能否用@cache实现递归自底向上解法？ #

我尝试用@cache实现递归自底向上解法，但代码无法正常运行：

from functools import cache
class Solution:    
                
    def minCostClimbingStairs(cost) -> int:
        @cache
        def minCostAux(step_i):
                
            if step_i == len(cost)-1: return minCosts[step_i]
            
            minCosts[step_i] = min(minCostAux(step_i-1) 
                                 , minCostAux(step_i-2, cost)) + cost[step_i] # 问题点
            
            return minCostAux(step_i+1) # 问题点
            
        cost.append(0) 
        return minCostAux(2, cost)

核心矛盾在于：自顶向下是通过递归子问题并返回当前解实现记忆化，而自底向上需要递归计算更大的问题（比如minCostAux(step_i+1)），我不知道如何将这两部分结合。我想要极简实现，不想显式维护缓存字典，想知道这种方式是否可行？

测试样例 #

print(Solution().minCostClimbingStairs([10,15,20])) # 预期输出：15
print(Solution().minCostClimbingStairs([1,100,1,1,1,100,1,1,100,1])) # 预期输出：6

内容的提问来源于stack exchange，提问作者Mahesha999