矩阵的最小路径和

题目：矩阵的最小路径和

《程序员代码面试指南》第57题 P185 难度：尉★★☆☆

本题看了迪杰斯特拉算法受到了启发，才想出来了。还是太菜了……

经典动态规划方法：

简单来说，就是生成和原矩阵一样大小的矩阵dp，dp[i][j]的值表示从(0,0)位置走到(i,j)位置的最小路径和。其中对于第一行和第一列的元素，它们的值就是沿着第一行或第一列的累加值（因为只能向右或者向下走）。对于其它位置的元素，它们的值为dp[i][j]=min{dp[i-1][j]，dp[i][j-1]}+m[i][j]。最右下角的值就是整个问题的答案。具体过程请参看如下代码中的minPathSum1方法。

public int minPathSum1(int[][] m) {
    if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
        return 0;
    }
    int row = m.length;
    int col = m[0].length;
    int[][] dp = new int[row][col];
    dp[0][0] = m[0][0];
    for (int i = 1; i < row; i++) {
        dp[i][0] = dp[i - 1][0] + m[i][0];
    }
    for (int j = 1; j < col; j++) {
        dp[0][j] = dp[0][j - 1] + m[0][j];
    }
    for (int i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
        }
    }
    return dp[row - 1][col - 1];
}

不过该方法的额外空间复杂度为O(M×N)。时间复杂度为O(M×N)。

动态规划经过空间压缩后的方法：

可以将额外空间复杂度降为O(min{M,N})，仅仅使用大小为min{M,N}的arr数组。

整个过程其实就是不断滚动更新arr数组，让它依次变成dp矩阵每一行或者每一列的值（看哪个最小），最终变成dp矩阵最后一行or列的值。

public int minPathSum2(int[][] m) {
    if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
        return 0;
    }
    int more = Math.max(m.length, m[0].length); // 行数与列数较大的那个为more
    int less = Math.min(m.length, m[0].length); // 行数与列数较小的那个为less
    boolean rowmore = more == m.length; // 行数是不是大于等于列数
    int[] arr = new int[less]; // 辅助数组的长度仅为行数与列数中的最小值
    arr[0] = m[0][0];
    for (int i = 1; i < less; i++) {
        arr[i] = arr[i - 1] + (rowmore ? m[0][i] : m[i][0]);
    }
    for (int i = 1; i < more; i++) {
        arr[0] = arr[0] + (rowmore ? m[i][0] : m[0][i]);
        for (int j = 1; j < less; j++) {
            arr[j] = Math.min(arr[j - 1], arr[j])
                + (rowmore ? m[i][j] : m[j][i]);
        }
    }
    return arr[less - 1];
}

同时，因为二维数组变成了一维数组，所以每次只需要一次寻址，程序的常数时间也得到了一定的加速。

但是需要注意，如果本题改成“打印具有最小路径和的路径”或其它求最优解的具体路径的问题，这些问题往往需要完整的动态规划表，此时不能用压缩空间的方法。如果只是想求最优解的值，则可以使用。因为空间压缩的方法是滚动更新的，会覆盖之前求解的值，让求解轨迹变得不可回溯。