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

Question

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

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;
        }
    }

示例输入：

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

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

Answer 1

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

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

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

这直接转化为以下递归记忆解决方案（代码在 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)))

如果您不允许跨过负值（即使这会保证更大的总和），则更改是微不足道的（如果没有路径，您需要指定 return左列到右列）。

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

Maximum sum of path from left column to right column

algorithm

graph

dynamic-programming

data-structures