动态规划:最小成本路径通过矩阵-回忆录？

Question

有一个简单的方法来回溯结果吗？我的动态编程解决方案可能会多次调用相同的函数，具有相同的参数。

我想回忆录会增加速度。然而，我不知道什么是最好的方法。这是最初的函数，虽然它没有回忆录，但它起作用了：

def dim(M):
    rows = len(M)
    cols = len(M[0])
    return rows, cols

def minimumCostPath(matrix, i=0, j=0, total=0):
    r,c = dim(matrix)
    if i+1 < r and j+1 < c:
        down = matrix[i+1][j]
        right = matrix[i][j+1]
        return min(minimumCostPath(matrix, i+1, j, total+down),
                    minimumCostPath(matrix, i, j+1, total+right))
    elif i+1 < r:
        right = matrix[i+1][j]
        return minimumCostPath(matrix, i+1, j, total+right)
    elif j+1 < c: 
        down = matrix[i][j+1]
        return minimumCostPath(matrix, i, j+1, total+down)
    else:
        return total + matrix[0][0]       

test = [ [23,70,54], 
         [86,5,13], 
         [86,62,77], 
         [60,37,32], 
         [88,58,98] ]
total = minimumCostPath(test)
>>>
318

下面是我尝试用一个矩阵(嵌套列表)来回溯这个函数。

def solution(matrix):
  cache = [[0 for j in range(len(matrix[0]))] for i in range(len(matrix))] 
  return helper(matrix, cache, i=0, j=0, total=0) 

def helper(matrix, cache, i=0, j=0, total=0):
    r,c = dim(matrix)
    if i+1 < r and j+1 < c:
        down = matrix[i+1][j]
        right = matrix[i][j+1]
        
        if cache[i+1][j] > 0:
          go_down = cache[i+1][j] + down
        else:
          go_down = helper(matrix, cache, i+1, j, total+down)
          cache[i+1][j] = go_down
        
        if cache[i][j+1] > 0 :
          go_right = cache[i][j+1] + right
        else:
          go_right = helper(matrix, cache, i, j+1, total+right)
          cache[i][j+1] = go_right 
        
        return min(go_down, go_right)
    elif i+1 < r:
        down = matrix[i+1][j]
        if cache[i+1][j] > 0:
          go_down = cache[i+1][j] + down
        else:
          go_down = helper(matrix, cache, i+1, j, total+down)
          cache[i+1][j] = go_down  
          return go_down     
    
    elif j+1 < c: 
        right = matrix[i][j+1]
        if cache[i][j+1] > 0 :
          go_right = cache[i][j+1] + right
        else:
          go_right = helper(matrix, cache, i, j+1, total+right)
          cache[i][j+1] = go_right         
        return go_right
    
    else:
        return total + matrix[0][0]


solution(test)

两个问题。

1. I得到了一个错误，TypeError: '<' not supported between instances of 'NoneType' and 'int'第23行将go_right或go_down计算为None，这是很奇怪的。
2. ，它不是很简洁，也不是很漂亮。也许一个更好的帮助函数可以简化代码。

最后，我理解有一种自下而上的方法，它不使用递归，而是迭代地填充表单元格。此时，我想知道递归解决方案如何利用回忆录，而不是从头开始，自下而上地实现。

Answer 1

首先，您的bug:在其中一个分支中，return go_down缩进过远，因此go_down的非递归计算不会返回值；相反，它会从函数的末尾掉下来并返回隐式None。

就回忆录而言，cache和lru_cache在functools中都有装饰者。上一次我使用它(大约5年前和许多版本之前)，它有点慢，只对外部数据(磁盘或网络)非常有用；您必须衡量它对您的性能是否令人满意。从那以后它可能有了很大的进步。

如果您确实需要手动实现缓存(如果functools.cache装饰器被证明太慢)，使用单独缓存的模式可能更好，以避免混合考虑：

minimumCostPath_cache = {}

def minimumCostPath(matrix, i=0, j=0):
    try:
        return minimumCostPath_cache[i, j]
    except KeyError:
        result = minimumCostPath_cache[i, j] = minimumCostPath_raw(matrix, i, j)
        return result

def minimumCostPath_raw(matrix, i=0, j=0):
   ...

为了避免全局变量和具有相互干扰的不同矩阵的调用，您可以在一个类中这样做：

class MinimumCostPath:
    def __init__(self, matrix):
        self.cache = {}
        self.matrix = matrix

    def calculate(self, i=0, j=0):
        try:
            return self.cache[i, j]
        except KeyError:
            result = self.cache[i, j] = self.calculate_uncached(i, j)
            return result

    def calculate_uncached(self, i=0, j=0):
        ...

Answer 2

如果您有Python3.9，那么了解一下@cache装饰器，以便实现无需担心的回忆录

@cache
def factorial(n):
    return n * factorial(n-1) if n else 1

>>> factorial(10)      # no previously cached result, makes 11 recursive calls
3628800
>>> factorial(5)       # just looks up cached value result
120
>>> factorial(12)      # makes two new recursive calls, the other 10 are cached
479001600

来源：https://docs.python.org/3/library/functools.html

Answer 3

from functools import lru_cache
@lru_cache(maxsize=None, typed=False)
def minimumCostPath(matrix, i=0, j=0):
    r,c = len(M), len(M[0])
    if i+1 < r and j+1 < c:
        down = matrix[i+1][j]
        right = matrix[i][j+1]
        return min(minimumCostPath(matrix, i+1, j) + down,
                    minimumCostPath(matrix, i, j+1) + right)
    elif i+1 < r:
        right = matrix[i+1][j]
        return minimumCostPath(matrix,i+1, j) + right
    elif j+1 < c: 
        down = matrix[i][j+1]
        return minimumCostPath(matrix,i, j+1) + down
    else:
        return matrix[0][0]

将总参数移出并使用lru_cache保存以前的函数调用。它有8次命中，15次未命中，现在的大小为15次。