如何将下面的递归dp转换为iterati

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]