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

开始慢慢习惯这种题目

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
      int row = matrix.size(), col = matrix[0].size();
      //  dp[i][j] 代表i*j大小矩阵的最大路径和
      std::vector<std::vector<int>> dp(row + 1, std::vector<int>(col + 1, 0));
      
      //  注意下标的差别
      //  对于dp来讲，下标+1代表当前结点
      for (int i = 0; i < row; ++i) {
        for (int j = 0; j < col; ++j) {
          //  只有一行
          if (i == 0 && j == 0) {
            dp[i + 1][j + 1] = matrix[i][j];
            continue;
          }
          if (i == 0) {
            dp[i + 1][j + 1] = matrix[i][j] + dp[i + 1][j];
            continue;
          }
          if (j == 0) {
            dp[i + 1][j + 1] = matrix[i][j] + dp[i][j + 1];
            continue;
          }
          dp[i + 1][j + 1] = matrix[i][j] + std::min(dp[i][j + 1], dp[i + 1][j]);
        }
      }
      
      return dp[row][col];
    }
};