题解 | 矩阵的最小路径和

class Solution {
public:
    //思路：求从左上角到右下角的路径最小，如果从左上角进行回溯递归的话，每一条路径会进行计算，每一个点都会进行计算多次；
    //如果从右下角开始，此点只能由上边和左边进行得到，也就是进行二选一，选择路径最短即可，那么相当于有了子问题：到这两个点最短路径是多少；也就是动态规划
    int minPathSum(vector<vector<int> >& matrix) {
        vector< vector<int> > dp( matrix.size(), vector<int>(matrix[0].size()) );

        dp[0][0] = matrix[0][0];
        for(int j=1; j<matrix[0].size(); ++j){
            dp[0][j] = dp[0][j-1] + matrix[0][j];
        }

        for(int i=1; i<matrix.size(); ++i){
            dp[i][0] = dp[i-1][0] + matrix[i][0];
        }

        for(int i =1; i<matrix.size(); i++){
            for(int j=1; j<matrix[0].size(); j++){
                dp[i][j] = min( dp[i-1][j], dp[i][j-1] ) + matrix[i][j];
            }
        }

        return dp.back().back();
    }
};