python - 我如何将以下递归 dp 转换为迭代

Question

我正在尝试将以下递归代码转换为自下而上/迭代动态规划。但是我无法弄清楚我应该迭代的顺序，因为状态取决于下一个和上一个索引。

matrix = [[-1, 4, 5, 1],
      [ 2,-1, 2, 4],
      [ 3, 3,-1, 3],
      [ 4, 2, 1, 2]]
rows = len(matrix)
cols = len(matrix[0])
cache = {}

def maxsum(dir, x, y):
   key = (dir, x, y)
   if key in cache: return cache[key]
   base = matrix[y][x]
   if x < cols-1:
       best = base + maxsum(2, x+1, y)
   else:
       best = base
   if dir != 0 and y > 0:
       best = max(best, base + maxsum(1, x, y-1))
   if dir != 1 and y < rows-1:
       best = max(best, base + maxsum(0, x, y+1))
   cache[key] = best
   return best

是否可以将此代码转换为迭代代码？如果是，请帮助我确定迭代顺序。

'dir' 可以取 0-2 之间的值。

x 和 y 将在 1 到 1000 之间。

我不想使用堆栈来解决这个问题。我想使用通用的迭代循环来解决这个问题，就像我们在自下而上的动态规划中所做的那样。

Answer 1

大意是想象递归调用图/树，叶子节点是什么；然后，迭代解决方案就是从叶节点开始迭代构建树，一直到根。

当然，这说起来容易做起来难，但通常问题的结构可以帮助您建立直觉。在这种特殊情况下，这是二维网格。

直觉

让我们从建立一些直觉开始。查看代码中的分支。他们决定你是否在特定情况下递归。它们对应什么？ 什么时候不递归？依次是:

• 网格的右边缘
• 网格的上边缘
• 网格的底边

我们需要先构建这些。

基本案例

问问自己:在什么情况下我们根本不会递归？这是基本情况。排名不分先后，它们是:

• 网格的右上角，dir=1
• 网格的右下角，dir=0

递归情况

最后，问问自己:从我们拥有的值开始，我们可以计算出什么？

• 对于右上角，我们可以计算dir=1的整个右边缘
• 对于右下角，我们可以计算dir=0的整个右边缘

据此，我们可以计算出 dir=2 的整个右边缘。

既然我们已经填充了右边缘的值，那么我们可以计算什么呢？记住上面的特殊情况。 仅依赖右边缘的单元格是紧靠右边缘左侧的顶部和底部边缘的两个单元格，dir=1 和 dir=0，分别。

有了它，我们现在可以为 dir=1 和 dir=0 计算右数第二列，因此 dir=2.

重复直到找到所需单元格的值。

代码

注意:这有点次优，因为它填满了整个表格，但足以说明这个想法。

def fill(dir, x, y):
    base = matrix[y][x]
    if x < cols-1:
        best = base + cache[2, x + 1, y]
    else:
        best = base
    if dir != 0 and y > 0:
        best = max(best, base + cache[1, x, y - 1])
    if dir != 1 and y < rows - 1:
        best = max(best, base + cache[0, x, y + 1])
    cache[dir, x, y] = best


def maxsum(dir, x, y):
    for i in range(cols - 1, -1, -1):
        for j in range(rows - 1, -1, -1):
            fill(0, i, j)
        for j in range(rows):
            fill(1, i, j)
        for j in range(rows):
            fill(2, i, j)
    return cache[dir, x, y]