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

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

方法一:递归法(超时) 具体做法: 容易想到的是,在第一步时可以选择向右或者向下,只需要当前的路径值加上(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),构建了辅助数组