题意理解

从矩阵的（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，大小为矩阵的结点数。