题意理解

从矩阵的(0,0)位置开始,向右或者向下移动到(n-1, m-1)位置,求经过的位置上的数字之和的最小值。

方法一(动态规划)

动态规划要求整体的最优解可以由子问题的最优解得到。
使用表示从(0,0)到(i,j)的路径和。
本题中,(i,j)只能从(i-1,j)或者(i,j-1)走过来,我们只要选择其中dp值较小的路径。(注意这里的子问题不是的最小值)
所以动态规划的公式为:
        
边界条件有:
1、
2、第0行和第0列的各个位置只能从前一个位置走过来,
    
    
算法示意图如下:
图片说明
最后可以发现,每个位置(i,j)只经过一次,所以经过时可以把更新为从(0,0)到(i,j)的最短路径和,这样可以不用开辟新数组dp,从而节省空间。

具体代码如下:

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();//求矩阵的长
        for (int i=1;i<m;i++) matrix[0][i] += matrix[0][i-1];//处理第0行
        for (int i=1;i<n;i++) matrix[i][0] += matrix[i-1][0];//处理第0列
        //更新每个matrix[i][j],使其记录从matrix[0][0]到它的最小路径和
        for (int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                matrix[i][j] += min(matrix[i-1][j], matrix[i][j-1]);
            }
        }
        return matrix[n-1][m-1];//注意返回值的下标
    }
};

时间复杂度:。一个双重for循环,从左到右从上到下地遍历了一遍矩阵。
空间复杂度:。所用空间为matrix,没有开辟新的空间。

方法二(递归)

使用表示从(0,0)到(i,j)的路径和。
递归的思路为:要求到位置(i,j)的最短路径和,需要已知到位置(i-1,j)和(i,j-1)的最短路径和。
递归公式为:
        
同时要注意第0行和第0列最为边界要特殊处理。
同样的,再求的时候,需要先求。可以看到,被重复计算了。所以使用一个map记录已经求过的,用i,j值作为key。
具体代码如下:

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    map<string, int> cost;//记录到(i,j)位置时的最短路径和
    int minpathsum(vector<vector<int> >& matrix, int i, int j) {
        //(0,0)位置cost等于matrix
        if (i==0 && j==0){
            return matrix[i][j];
        }
        string key = to_string(i) + "," + to_string(j);
        //判断(i,j)位置的最短路径是否被计算过了
        if (cost.find(key)!=cost.end()){
            return cost[key];
        }
        int ans = 0;
        //递归调用过程,第0行和第0列要分开处理
        if (i==0){
            ans = matrix[i][j] + minpathsum(matrix, i, j-1);
        }
        else if (j==0){
            ans = matrix[i][j] + minpathsum(matrix, i-1, j);
        }
        else{
            ans = matrix[i][j] + min(minpathsum(matrix, i-1, j), minpathsum(matrix, i, j-1));
        }
        cost.insert(pair<string, int>(key,ans));
        return ans;
    }

    int minPathSum(vector<vector<int> >& matrix) {
        int n = matrix.size();//求矩阵的宽
        int m = matrix[0].size();//求矩阵的长
        return minpathsum(matrix, n-1, m-1);//注意返回值的下标
    }
};

时间复杂度:。对于每一个位置(i,j),只会递归调用一次,所以时间复杂度在于总共的结点数,N和M分别为矩阵的宽和长。
空间复杂度:。新开辟了一个map,大小为矩阵的结点数。