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

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

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

我的解决方案的问题是它应该达到2（在最后一行第2列），通过4->3->3->2，但我的解决方案把2放在访问状态，所以它不会检查它如果我移除访问过的数组，它将被困在任何单元格上的上、下、上、下无限循环中。
编辑：每个点只能访问一次。

最佳答案

这个问题可以用线性规划的方法解决，但有一个小的转折，因为你不能访问每个细胞不止一次，但运动实际上可以带你到那个条件。
然而，要解决这个问题，你可以注意到在给定的位置上
刚从(x, y)到达(x, y)，因此允许您向上、向下或向右（当然，除非您在边缘）
从(x-1, y)到达(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)))

如果不允许跨过负值（即使这可以保证较大的总和），则更改很小（如果没有从左列到右列的路径，则需要指定返回什么）。

关于algorithm - 从左列到右列的最大路径总和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32807349/