class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        // write code here
        if(matrix.empty() || matrix[0].empty()) return 0;
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int> > dp(m,vector<int>(n,0));
        for(int i=0;i<m;i++) for(int j=0;j<n;j++){
            if(i-1>=0 && j-1>=0) {
                if(dp[i-1][j]<dp[i][j-1]) dp[i][j] = dp[i-1][j]+matrix[i][j];
                else dp[i][j] = dp[i][j-1]+matrix[i][j];
            }else if(i==0 && j==0){
                dp[0][0] = matrix[0][0];
            }else if(i==0 && j!=0){
                dp[i][j] = dp[i][j-1]+matrix[i][j];
            }else if(i!=0 && j==0){
                dp[i][j] = dp[i-1][j]+matrix[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};