arrays - 2D数组中的最大路径总和

Question

考虑以下问题：
给定一个无符号整数和最大长度n的2D数组，在该矩阵中找到一个不大于n且最大化总和的路径。输出应该包含路径和总和。
路径由相邻整数组成，这些整数要么都在同一行中，要么都在同一列中，要么都在右下角的对角线上。
例如，考虑以下矩阵和给定的路径长度限制3：

 1  2  3  4  5    
 2  1  2  2  1   
 3  4  5* 6  5    
 3  3  5 10* 5    
 1  2  5  7 15* 

最理想的路径是 5 + 10 + 15（节点用 *标记）。
现在，当看到这个问题时，考虑到这个问题与 Min Cost Path或 Maximum Sum Rectangular Submatrix之类的其他问题相似，动态编程解决方案在这里似乎是最合适的问题是，为了正确地解决这个问题，您需要从矩阵中的每个整数（节点）开始构建路径，而不仅仅是从左上角开始到右下角结束。
我最初想的是一种类似于 Maximum Sum Rectangular Submatrix解决方案的方法，在这种方法中，我可以存储来自每个节点的每个可能的路径（路径长度小于n，仅向右/向下），但我可以设想的唯一方法是从每个节点发出向下和向右的递归调用，这似乎违背了dp的目的。另外，我需要能够存储最大路径。
我想的另一个可能的解决方案是以某种方式调整最长路径搜索，并从图中的每个int运行它，其中每个int就像一个边权重。
找到最大路径的最有效方法是什么？

Answer 1

这里的挑战是避免将相同的节点求和超过一次。为此，您可以应用以下算法：
算法
对于三个方向（向下、向下+向右、向右）中的每一个方向，执行步骤2和3：
确定在这个方向上存在的行数。对于向下的方向，这是列数。对于向右的方向，这是行数。对于对角线方向，这是对角线的数量，即行数和列数之和减去1，如下面的红线所示：

对于每一行，请执行以下操作：
确定该行上的第一个节点（称为“head”），并将“tail”设置为同一个节点。这两个引用引用“当前”路径的端点。同时将总和和路径长度设置为零。
对于当前行上的每个头部节点，执行以下项目符号：
将头节点的值添加到和中并增加路径长度
如果路径长度大于允许的最大值，则从总和中减去尾部的值，并将尾部设置为在当前行上跟随它的节点。
当总和大于迄今为止发现的最大总和时，记住它和路径的位置。
将head设置为当前行上跟随它的节点
最后返回最大和以及生成该和的路径。
代码
下面是一个基本JavaScript实现：

function maxPathSum(matrix, maxLen) {
    var row, rows, col, cols, line, lines, dir, dirs, len,
        headRow, headCol, tailRow, tailCol, sum, maxSum;

    rows = matrix.length;
    cols = matrix[0].length;
    maxSum = -1;
    dirs = 3; // Number of directions that paths can follow
    if (maxLen == 1 || cols == 1) 
        dirs = 1; // Only need to check downward directions

    for (dir = 1; dir <= 3; dir++) {
        // Number of lines in this direction to try paths on
        lines = [cols, rows, rows + cols - 1][dir-1];
        for (line = 0; line < lines; line++) {
            sum = 0;
            len = 0;
            // Set starting point depending on the direction
            headRow = [0, line, line >= rows ? 0 : line][dir-1];
            headCol = [line, 0, line >= rows ? line - rows : 0][dir-1];
            tailRow = headRow;
            tailCol = headCol;
            // Traverse this line
            while (headRow < rows && headCol < cols) {
                // Lengthen the path at the head
                sum += matrix[headRow][headCol];
                len++;
                if (len > maxLen) {
                    // Shorten the path at the tail
                    sum -= matrix[tailRow][tailCol];
                    tailRow += dir % 2;
                    tailCol += dir >> 1;
                }
                if (sum > maxSum) {
                    // Found a better path
                    maxSum = sum;
                    path = '(' + tailRow + ',' + tailCol + ') - ' 
                         + '(' + headRow + ',' + headCol + ')';
                }
                headRow += dir % 2;
                headCol += dir >> 1;
            }
        }
    }
    // Return the maximum sum and the string representation of
    // the path that has this sum
    return { maxSum, path };
} 

// Sample input
var matrix = [
    [1,  2,  3,  4,  5],
    [2,  1,  2,  2,  1],
    [3,  4,  5,  5,  5],
    [3,  3,  5, 10,  5],
    [1,  2,  5,  5, 15],
];

var best = maxPathSum(matrix, 3);

console.log(best);

关于代码的一些细节
请注意，行/列索引从0开始。
头部和尾部坐标的递增方式基于dir变量的二进制表示：它接受这三个值（二进制表示法）：01、10、11
然后，您可以取第一位来指示方向上的下一步是否在下一列（1）上（0），取第二位来指示是否在下一行（1）上（0）。可以这样描述，其中00表示“当前”节点：

00 10
01 11

所以我们对dir的值有这个意义：
01:沿着柱子走
10:沿着那排走
11:斜行
代码使用 >>1提取第一位，使用 % 2提取最后一位在这两种情况下，该操作都将导致0或1，并且是需要添加到列或行中的值。
以下表达式创建1D数组并动态获取其值之一：

headRow = [0, line, line >= rows ? 0 : line][dir-1];

简称：

switch (dir) {
case 1:
    headRow = 0;
    break;
case 2:
    headRow = line;
    break;
case 3:
    if (line >= rows) 
        headRow = 0
    else 
        headRow = line;
    break;  
}

时空复杂性
头部将在每个方向访问每个节点一次。尾部将访问较少的节点方向的数目是恒定的，最大路径长度值不影响人头访问的数量，因此时间复杂度是：
Θ（行*列）
在这个算法中没有使用额外的数组，只有一些基本变量因此，额外的空间复杂度是：
_____（1）
这两个都是你能期待的最好的。
是动态编程吗？
在dp解决方案中，通常会使用某种表格或备忘录，可能是矩阵形式，其中为特定节点找到的每个子结果都是用于确定相邻节点的结果的输入。
这样的解决方案可能需要额外的空间但是这个问题可以在不占用大量空间的情况下解决。当一次只看一行（行、列或对角线）时，该算法与卡丹的算法有一些相似之处：
一个不同之处在于，扩展或缩短路径/子阵列的选择不依赖于矩阵数据本身，而是取决于给定的最大长度。这也与以下事实有关：这里所有的值都保证为非负，而卡丹的算法适用于有符号数字。
就像卡丹的算法一样，到目前为止最好的解是在一个单独的变量中保持的。
另一个区别是我们需要从三个方向看但这仅仅意味着在这三个方向重复相同的算法，同时传递迄今为止找到的最佳解。
这是动态编程的一个非常基本的用途，因为这里不需要制表或记忆技术我们只保留变量sum和maxSum的最佳结果这不能被视为小报或备忘录，它通常会记录一些必须在某个时候进行比较的竞争结果。见 this interesting answer on the subject。