题解 | #矩阵的最小路径和#

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    /*
        dp(i,j) 表示从(0,0)到(i,j)的路径和。
        dp(i,j) = min(dp(i-1,j),dp(i,j-1)) + matrix(i,j);
        对于只有一行或者一列的需初始化。--这个下了点功夫。
    */
    int minPathSum(vector<vector<int> >& matrix) {
        int colum = matrix.size(), line = matrix[0].size();
        vector<vector<int>> dp (colum, vector<int>(line, 0));
        for (int i = 0; i < colum; i++) {
            for (int j = 0; j < line; j++) {
                if(i == 0 && j == 0) { 
                    dp[i][j] = matrix[0][0];
                } else if (i == 0) {
                    dp[i][j] = dp[0][j - 1] + matrix[0][j];
                } else if (j == 0){
                    dp[i][j] = dp[i-1][0] + matrix[i][0];                    
                } else {
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j];
                }
            }
        }
        return dp[colum-1][line-1];        // write code here
    }
};