寻找二维网格最大成本路径的动态规划

Question

给定一个二维网格，G 有 q 行和 p 列，其中每个单元格 G[i][j] 包含一个整数。它需要从左上角 (0,0) 到右下角 (q-1,p-1)。我一次只能向右和向下移动 1 个单位。当我访问一个单元格时，单元格 G[i][j] 中的金额将添加到总数中。我需要最大化总数并获得路径。这是我的第一次尝试

def findMaxPerson1(q, p, grid, memo={}):
    key = f"{q},{p}"
    if key in memo:
        return memo[key]
    if q == 0 and p == 0:  # Start point
        return grid[0][0]
    if q < 0 or p < 0:
        return 0
    up = findMaxPerson1(q-1, p, grid, memo)  # Up
    left = findMaxPerson1(q, p-1, grid, memo)  # Left
    if up >= left:
        memo[key] = up + grid[q][p]
        return memo[key]
    else:
        memo[key] = left + grid[q][p]
        return memo[key]

我从上面的代码中得到了 15。现在我尝试修改以前的代码以获取路径和最大总数。这是我的尝试代码：

def findMaxPerson1(q, p, grid, memo={}):
        key = f"{q},{p}"
        if key in memo:
            return memo[key]
        if q == 0 and p == 0:
            return {
                'total': grid[q][p],
                'path': [(q, p)]
            }
        if q < 0 or p < 0:
            return None
        up = findMaxPerson1(q-1, p, grid, memo)  # Up
        left = findMaxPerson1(q, p-1, grid, memo)  # Left
        if up is not None and left is not None:  # Both are dictionary
            if up['total'] >= left['total']:
                up['total'] = up['total'] + grid[q][p]
                up['path'].append((q, p))
                memo[key] = up
                return up
            else:
                left['total'] = left['total'] + grid[q][p]
                left['path'].append((q, p))
                memo[key] = left
                return left
        if up is not None:
            up['total'] = up['total'] + grid[q][p]
            up['path'].append((q, p))
            memo[key] = up
            return up
        else:
            left['total'] = left['total'] + grid[q][p]
            left['path'].append((q, p))
            memo[key] = left
                return left

    print(findMaxPerson1(2, 1, grid, {}))

使用具有相同网格的修改后的代码，我得到了这个输出：

{'total': 19, 'path': [(0, 0), (1, 0), (1, 1), (2, 0), (2, 1)]}

这是我使用的网格：

grid = [
    [1, 2],
    [3, 4],
    [5, 6],
]

为什么路径不正确？有谁知道我做错了什么？提前谢谢你。

Answer 1

第二种方法的问题在于，您正在重用和更新与 memo 中多个键的值相同的对象。

它是第一种方法，memo 的值是一个简单的整数，当您执行 memo[key] = up + grid[q][p] 时，该值被复制。现在 up 的值和 memo[key] 的值完全相互独立。

相比之下，在第二种方法中，您可以：

up['total'] = up['total'] + grid[q][p]
up['path'].append((q, p))
memo[key] = up

修改 up而不复制它，现在你在up和memo[key]中有相同的对象，它有相同的更新值。

解决这个问题的天真的方法是 deepcopy up 和 left 在修改之前，像这样：

import copy
...
up = copy.deepcopy(up)
left = copy.deepcopy(left)

这解决了问题，现在第二种方法打印：

{'total': 15, 'path': [(0, 0), (1, 0), (2, 0), (2, 1)]}

但这非常低效，因为它每次都复制整个路径，使您的算法 O(n⁴) 而不是 O(n²)。

更好的方法是只存储每个键的前一个键（而不是整个路径）。算法的主要部分完成后，您可以按照这个向后引用重建路径。

寻找二维网格最大成本路径的动态规划

Dynamic programming to find the maximum cost path of a 2D grid

python

algorithm

dynamic-programming