题解 | #矩阵的最小路径和#
矩阵的最小路径和
https://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb
class Solution { public: /** * * @param matrix int整型vector<vector<>> the matrix * @return int整型 */ int minPathSum(vector<vector<int>>& matrix) { int a = matrix.size(); int b = matrix.size() > 0 ? matrix[0].size() : 0; vector<vector<int>> dp(a + 1, vector<int>(b + 1, 0)); for (int i = 1; i <= a; i++) { for (int j = 1; j <= b; j++) { if (j == 1) dp[i][j] = matrix[i - 1][j - 1] + dp[i - 1][j]; else if (i == 1) dp[i][j] = matrix[i - 1][j - 1] + dp[i][j - 1]; else dp[i][j] = matrix[i - 1][j - 1] + min(dp[i - 1][j], dp[i][j - 1]); } } return dp[a][b]; } };