algorithm - 从左列到右列的路径的最大总和

Question

我正在尝试计算在网格中从左列到右列可以实现的最大总和。允许的 Action 是向上、向下、向右。我已经实现了这个解决方案(它是广度优先搜索):

for(int i=1; i<=n; i++) {
    Queue<Position> q = new LinkedList<Position>();
    q.add(new Position(i, 1));
    dp[i][1] = map[i][1];

    while(!q.isEmpty()) {
        Position node = q.poll();
        visited[node.n][node.m] = 1;
        if(dp[node.n][node.m] > max) {
            max = dp[node.n][node.m];
        }
        if(visited[node.n-1][node.m] != 1 && node.n != 1 && dp[node.n-1][node.m] < dp[node.n][node.m] + map[node.n-1][node.m] && map[node.n-1][node.m] != -1) {
            dp[node.n-1][node.m] = dp[node.n][node.m] + map[node.n-1][node.m];  

            q.add(new Position(node.n-1, node.m));
        }
        if(visited[node.n+1][node.m] != 1 && node.n != n && dp[node.n +1][node.m] < dp[node.n][node.m] + map[node.n+1][node.m] && map[node.n+1][node.m] != -1) {
            dp[node.n +1][node.m] = dp[node.n][node.m] + map[node.n+1][node.m];
            q.add(new Position(node.n + 1, node.m));
        }
        if(visited[node.n][node.m+1] != 1 && node.m != m && dp[node.n][node.m+1] < dp[node.n][node.m] + map[node.n][node.m+1] && map[node.n][node.m+1] != -1) {
            dp[node.n][node.m+1] = dp[node.n][node.m] + map[node.n][node.m+1];
            q.add(new Position(node.n, node.m+1));
        }

    }
}
static class Position {
        int n, m;
        public Position(int row, int column) {
            this.n = row;
            this.m = column;
        }
    }

示例输入:

-1 4 5 1
2 -1 2 4
3 3 -1 3
4 2 1 2

我的解决方案的问题是它应该通过 4->3->3->2 达到 2(在最后一行第 2 列)，但我的解决方案将 2 置于已访问状态，因此它不会检查它。如果我删除已访问的数组，它将陷入无限循环，在任何单元格上向上、向下、向上、向下。

编辑:每个点只能访问一次。

Answer 1

这个问题可以用线性规划方法解决，但有一个小问题，因为你不能多次访问每个单元格，但移动实际上可以将你带到那个条件。

要解决此问题，您可以注意在给定位置 (x, y)你要么

• 刚刚到达 (x, y)来自 (x-1, y)因此，您可以向上、向下或向右移动(当然，除非您在边缘)
• 到达 (x, y)来自 (x, y-1) (即从上方)然后你只能向下或向右
• 到达 (x, y)来自 (x, y+1) (即从下面)然后你只能向上或向右

这直接转化为以下递归内存解决方案(代码在 Python 中):

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("left", x+1, y)
    else:
        best = base
    if dir != "above" and y > 0:
        best = max(best, base + maxsum("below", x, y-1))
    if dir != "below" and y < rows-1:
        best = max(best, base + maxsum("above", x, y+1))
    cache[key] = best
    return best

print(max(maxsum("left", 0, y) for y in range(rows)))

如果您不允许跨过一个负值(即使这会保证更大的总和)，则更改是微不足道的(如果没有从左列到右列的路径，您需要指定要返回的内容) .