算法题练习 -- 矩阵的最小路径和

hello，大家好，欢迎来到银之庭。我是 Z，一个普通的程序员。今天我们来做一道动态规划方面的入门算法题：求矩阵的最小路径和。

1. 题目

给出一个 int 型的矩阵 m，从左上角开始每次只能向下或向右移动一格，直到移动到右下角，经过的位置的数值和为路径和，求最小的路径和。如下面的矩阵：

路径 1，3，1，0，6，1，0 得到的路径和是最小的，为 12。

2. 思路分析

这道题是典型的动态规划能解决的问题，也是动态规划的入门题。动态规划的代码实现不难，重点是想出：

1. dp 表的格式;
2. 表里每一项代表什么含义;
3. dp 表的初始填入的项;
4. 计算 dp 表的推导公式.

一些比较难的动态规划的题目通常是这些东西不好想，一旦想到，代码实现也是比较简单的。

回到这道题目，我们可以比较容易地想到:

1. dp 表应该是和原矩阵一样的一个二维矩阵;
2. 矩阵里每一项是从左上角到当前位置的最小路径和;
3. dp 表的初始填入项是最上面一行和最左边一列的值，直接从起始位置沿直线到达指定位置的路径即最短路径，因为不能向上或向左移动，所以从起始位置到指定位置实际上只有一条路径，它的和一定是最短路径和;
4. 对矩阵其他任一位置 dp[i][j] 的值的计算公式为：min(dp[i][j-1], dp[i-1][j])+m[i][j]。即从起始位置到当前位置有两种可能：先走到当前位置的左边再向右移动，或先走到当前位置的上边再向下移动，我们已经知道了起始位置到当前位置的左边的最小路径和（即 dp[i][j-1]）和起始位置到当前位置的上边的最小路径和（即 dp[i-1][j]），从中取较小的那个加上当前位置的值就是起始位置到当前位置的最小路径和了。

构造完整个 dp 表后，取 dp 表右下角的位置的值，就是从起始位置到右下角位置的最小路径和了。

3. 代码实现

public static int getMinPathSum(int[][] m) {
        // 特殊情况校验
        if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
            return 0;
        }

        int[][] dp = new int[m.length][m[0].length];
        dp[0][0] = m[0][0]; // 填充起始位置的值
        for (int i = 1; i < dp.length; i++) { // 填充最左侧一列的值
            dp[i][0] = dp[i - 1][0] + m[i][0];
        }
        for (int j = 1; j < dp[0].length; j++) { // 填充最上面一行的值
            dp[0][j] = dp[0][j - 1] + m[0][j];
        }

        // 填充剩余位置的值
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
            }
        }

        // 右下角位置的值就是从左上角到右下角的最下路径和了
        return dp[m.length - 1][m[0].length - 1];
    }

代码中注释已经比较清楚了，理解了思路后看代码还是比较简单的。

4. 问题扩展

4.1 返回最小路径

如果题目要求不是返回最小路径和，而是返回最小路径和的路径的话，我们就需要根据已经构造完成的 dp 表从右下角开始，反推出到左上角的路径，再反转返回即可。反推的逻辑是：在 dp 表的任意位置 dp[i][j] 处，用 dp[i][j]-m[i][j] 得出值，看是等于 dp[i-1][j] 还是 dp[i][j-1]，由此判断是应该往左走，还是往上走。代码如下：

public static List<Integer> getMinPath(int[][] m) {
        // 特殊情况校验
        if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
            return new ArrayList<>();
        }

        int[][] dp = new int[m.length][m[0].length];
        dp[0][0] = m[0][0]; // 填充起始位置的值
        for (int i = 1; i < dp.length; i++) { // 填充最左侧一列的值
            dp[i][0] = dp[i - 1][0] + m[i][0];
        }
        for (int j = 1; j < dp[0].length; j++) { // 填充最上面一行的值
            dp[0][j] = dp[0][j - 1] + m[0][j];
        }

        // 填充剩余位置的值
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
            }
        }

        // 从右下角开始往左上角走
        int i = m.length - 1;
        int j = m[0].length - 1;
        List<Integer> path = new ArrayList<>();
        path.add(m[i][j]);
        while (i > 0 && j > 0) {
            if (dp[i][j] - m[i][j] == dp[i - 1][j]) {
                path.add(m[i - 1][j]);
                i--;
            } else {
                path.add(m[i][j - 1]);
                j--;
            }
        }

        // 到达最左侧或最上侧后直接把剩余一行或一列的值加上
        if (i > 0) {
            i--;
            for (; i >= 0; i--) {
                path.add(m[i][0]);
            }
        } else {
            j--;
            for (; j >= 0; j--) {
                path.add(m[0][j]);
            }
        }

        // 翻转返回
        Collections.reverse(path);
        return path;
    }

4.2 dp 表压缩

如果题目只要求返回最小路径和的话，实际上我们不需要保留完整的 dp 表，只需要保留一行的 dp 数据即可，从上到下，先计算出第一行的 dp 数据，再根据第一行的数据依次计算第二行的数据，得到第二行的数据后，第一行的数据就没用了，可以丢弃，继续计算第三行的数据，直到最后一行。当然，只保留一列效果一样，可以根据原矩阵的形状来决定，按行优化的代码如下：

public static int getMinPathSum2(int[][] m) {
        // 特殊情况校验
        if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
            return 0;
        }

        // 第一行数据
        int[] dpRow = new int[m[0].length];
        dpRow[0] = m[0][0];
        for (int j = 1; j < m[0].length; j++) {
            dpRow[j] = dpRow[j - 1] + m[0][j];
        }

        // 循环计算后续每一行数据
        for (int i = 1; i < m.length; i++) {
            dpRow[0] = dpRow[0] + m[i][0];
            // 滚动更新数组每一项
            for (int j = 1; j < m[0].length; j++) {
                dpRow[j] = Math.min(dpRow[j - 1], dpRow[j]) + m[i][j];
            }
        }

        return dpRow[m[0].length - 1];
    }