题解 | #矩阵的最小路径和#

思路： 从题目中给出的信息：

• 不会是空矩阵，矩阵值都是非负数
• 只能往右或者往下，不能返回，因此路径长度会累加 故常用的方法便是递归或者动态规划。

方法一：递归法（超时） 具体做法： 容易想到的是，在第一步时可以选择向右或者向下，只需要当前的路径值加上(n,m-1)或者(n-1,m)的矩阵路径即可，加上谁，自然是其中较小者。而(n,m-1)与(n-1,m)又是(n,m)的子问题，可以继续递归下去。只需要用i，j表示当前位置，后续限制边界的向下或者向右即可。这是容易想到的方法，缺点是重复计算太多，会超时。 下图为从(0，0)开始的每个子问题的递归方向，每次可以选择向下或者是向右递归，以缩短为子问题：

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPath(vector<vector<int> >& matrix, int i, int j){
        int n = matrix.size();
        int m = matrix[0].size();  //因为n,m均大于等于1
        //当i的值为n-1且j的值为m-1时,走到了右下角
        if(i == n - 1 && j == m - 1)
            return matrix[i][j]; //直接返回右下角的数值
        //当i的值为n- 1且j的值不为m- 1时，只能往右走
        if(i == n - 1 && j != m - 1)
            return matrix[i][j] + minPath(matrix, i ,j + 1);
        else if(i != n - 1 && j == m - 1)  //反之，只能往下走
            return matrix[i][j] + minPath(matrix, i + 1, j);
        //其他情况都可以走，选择子问题中最短的加上此时的数字即可
        int a =  minPath(matrix, i, j + 1);
        int b =  minPath(matrix, i + 1, j);
        return a < b ? matrix[i][j] + a : matrix[i][j] + b;
    }
    int minPathSum(vector<vector<int> >& matrix) {
        return minPath(matrix, 0, 0);
    }
};

复杂度分析：

• 时间复杂度：O(2^n)，一步需要两个子递归
• 空间复杂度：O(n)， 递归栈最大深度

方法二：递归改进（空间记忆搜索） 具体做法：因为递归是优先计算低级子问题，由此重复计算了很多子问题，导致超时，因此可以用一个dp二位数组来记录曾经算过的值，递归过程用到时直接用数组的值而不需要重新进行子递归。

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int dp[2001][2001];
    int minPath(vector<vector<int> >& matrix, int i, int j){
        int n = matrix.size();
        int m = matrix[0].size();  //因为n,m均大于等于1
        //当i的值为n-1且j的值为m-1时,走到了右下角
        if(i == n - 1 && j == m - 1)
            return dp[i][j] = matrix[i][j];  //直接返回右下角的数值
        //当i的值为n- 1且j的值不为m- 1时，只能往右走
        if(i == n - 1 && j != m - 1){
            if(dp[i][j + 1] != -1){    //若是之前计算过这部分就不需要重复计算，直接用
                return matrix[i][j] + dp[i][j + 1];
            }
            else{
                dp[i][j + 1] = minPath(matrix, i ,j + 1);  //若是没有，则计算后储存
                return matrix[i][j] + dp[i][j + 1];
            }
        }
        else if(i != n - 1 && j == m - 1)  //反之，只能往下走
            if(dp[i + 1][j] != -1){
                return matrix[i][j] + dp[i + 1][j];
            }
            else{
                dp[i + 1][j] = minPath(matrix, i + 1 ,j);
                return matrix[i][j] + dp[i + 1][j];
            }
        //其他情况都可以走，选择子问题中最短的加上此时的数字即可,利用好dp数组中存储的计算过的信息
        int a = 0, b = 0;
        if(dp[i][j + 1] != -1)
            a = dp[i][j + 1];
        else{
            dp[i][j + 1] = minPath(matrix, i, j + 1);
            a = dp[i][j + 1];
        }
        if(dp[i + 1][j] != -1)
            b = dp[i + 1][j];
        else{
            dp[i + 1][j] = minPath(matrix, i + 1, j);
            b = dp[i + 1][j];
        }
        return a < b ? matrix[i][j] + a : matrix[i][j] + b;
    }
    int minPathSum(vector<vector<int> >& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        for(int i = 0; i < n; i++)     //初始化dp数组为-1
            for(int j = 0; j < m; j++)
                dp[i][j] = -1;
        return minPath(matrix, 0, 0);
    }
};

复杂度分析：

• 时间复杂度：O(nm)，遍历了整个二维数组
• 空间复杂度：O(nm)，dp二维数组的构建

方法三：动态规划

1. 设置dp[i][j]表示当前(i,j)位置时的最短路径；
2. 确立公式，当前的最短路径为dp[i][j]，则上一步要么是(i,j-1)往右，要么是(i-1,j)往下，则取其中较小的值即可得到当前公式：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]；
3. 确立边界，第一行：dp[0][j] = dp[0][j-1]+ matrix[0][j]，第一列：dp[i][0] = dp[i-1][0]+ matrix[i][0]，因为要在第一行必须是往右移动，要在第一列必须是往下移动；
4. 最后dp[n-1][m-1]即为所求的最短路径。

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();  //因为n,m均大于等于1
        int dp[2001][2001] = {0};
        dp[0][0] = matrix[0][0];//dp[i][j]表示以当前i，j位置为终点的最短路径长度
        for(int i = 1; i < n; i++)//处理第一列
            dp[i][0] = matrix[i][0] + dp[i-1][0];
        for(int j = 1; j < m; j++)//处理第一行
            dp[0][j] = matrix[0][j] + dp[0][j-1];
        for(int i = 1; i < n; i++){ //其他按照公式来
          for(int j = 1; j < m; j++){
              dp[i][j] = matrix[i][j] + (dp[i-1][j] > dp[i][j-1] ? dp[i][j-1] : dp[i-1][j]);
          }
      }
       return dp[n-1][m-1];
    }
};

复杂度分析：

• 时间复杂度：O(nm)，每个元素遍历一次
• 空间复杂度：O(nm)，构建了辅助数组