【手撕代码】矩阵最小路径问题（递归+动态规划）

本是古典何须时尚 2022-02-15 02:11 236阅读 0赞

> 题目：给你一个二维数组，二维数组中的每个数都是正数，要求从左上角走到右下角，每一步只能向右或者向下。沿途经过的数字要累加起来。返回最小的路径和。

### **一、递归版本** ###

*  如果矩阵为 n x n，那么时间复杂度为：O(![2^\{n^\{2\}\}][2_n_2])。

递归版本虽然简单，但是时间复杂度过高，显然是不行的。通过分析发现，在递归过程中，会有很多重复的计算，如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

在计算(1,0)位置的右元素和计算(0,1)位置的下元素时，发生了重复计算：都是计算（1,1）位置到右下角的最小距离和。这里只是分析了两步，如果继续分析，会出现很多类似的重复计算过程。

*  **递归版本代码实现**

public class MinPathInMatrixWithRecursion {
    
        public static int minPath(int[][] matrix){
            if(matrix == null || matrix.length < 1 || matrix[0].length < 1){
                return 0;
            }
            // 从矩阵的左上角走到右下角
            return process(matrix, 0, 0);
        }
    
        /**
         * @param matrix : 矩阵
         * @param i ： 当前位置的行号
         * @param j ：当前位置的列号
         * @return ：到达最后位置时的最小路径和
         */
        public static int process(int[][] matrix, int i, int j){
            if(i == matrix.length - 1 && j == matrix[0].length - 1){
                // 当前位置已经在右下角了
                return 0;
            }
    
            // 当前位置处在最后一行时，只能向右走
            if(i == matrix.length - 1){
                return  matrix[i][j] + process(matrix, i, j + 1);
            }
    
            // 当前位置处在最后一列时，只能向下走
            if(j == matrix[0].length - 1){
                return matrix[i][j] + process(matrix, i + 1, j);
            }
    
            // 普通位置：取左边位置和右边位置到右下角位置距离最小的那个
            int right = matrix[i][j] + process(matrix, i, j + 1);
            int down = matrix[i][j] + process(matrix, i + 1, j);
            return Math.min(right,down);
        }
    }

### 二、记忆化搜索版本 ###

那么我们是不是可以利用缓存将每次的计算结果存储起来，下一次再碰到相同元素计算的时候先去缓存中查找看是否已经计算过了，如果存在则直接使用，在没有计算过的时候再去计算，并将结果存储到缓存中。很明显这样的缓存可以用map实现，元素对应key，结果对应value。

### 三、动态规划版本 ###

*  **改递归思路：**

利用 baseCase（即：i == matrix.length - 1 && j == matrix\[0\].length - 1）可以直接得出图中状态表右下角的位置为6，然后再由 6 推出最后一行和最右一列的状态值，然后又可以利用刚才推出的值进行新的一轮推到.....最终将整个表的每个位置都填上其对应的状态值。如下图所示：左上角位置状态值为17，即代表从左上角到右下角位置最短路径值为：17。

这个过程就盖楼一样，从地基开始，上层依赖下层。下层盖好了，上层就可以盖了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1][]

*  **动态规划版本代码实现：**

public class MinPathInMatrixWithDynamic {
    
        public static int minPath(int[][] matrix){
            if(matrix == null || matrix.length < 1 || matrix[0].length < 1){
                return 0;
            }
    
            // 从递归的过程可以看出来：可变参数：i、j
            int lastRow = matrix.length - 1;     // lastRow：代表最后一行的行号，所以要减1
            int lastCol = matrix[0].length - 1;
            // 构建可变参数为 i 和 j 的二维状态表,这里必须要+1，因为是矩阵的大小
            int[][] dp = new int[lastRow + 1][lastCol + 1];
    
            // 找递归过程的 baseCase,即不需要依赖其他状态的，即右下角位置
            // 右下位置到其本身的距离即为它本身的大小
            dp[lastRow][lastCol] = matrix[lastRow][lastCol];
    
            // 填充最后一行位置的 dp：从右往左推
            for(int i = lastRow, j = lastCol - 1; j >= 0; j--){
                // 左边位置的dp值等于右边位置的dp值加上自身的数值
                dp[lastRow][j] = matrix[lastRow][j] + matrix[lastRow][j + 1];
            }
            // 填充最后一列位置的 dp：从下往上推
            for(int i = lastRow, j = lastCol; i >= 0; i--){
                //
                dp[i][lastCol] = matrix[i][lastCol] + dp[i][lastCol];
            }
            // 填充一般位置的 dp（即：除最后一行和最后一列的位置）
            for(int i = lastRow - 1; i >= 0; i--){
                for(int j = lastCol - 1; j >= 0; j--){
                    // 一般位置：当前位置值 + min(下边位置的dp值, 右边位置的dp值)
                    dp[i][j] = matrix[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
                }
            }
            return dp[0][0];   // 返回目标位置的值
        }
    }

[2_n_2]: https://private.codecogs.com/gif.latex?2%5E%7Bn%5E%7B2%7D%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20220215/be8c51e785d04922b8349e06f85a87ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1]: /images/20220215/f5e95b1b69cb4c878000523de6480b3a.png