题解 | #矩阵的最小路径和#
矩阵的最小路径和
https://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb
matrix本身就可以作为状态数组
#include <vector> class Solution { public: int minPathSum(vector<vector<int> >& matrix) { int n = matrix.size(), m = matrix[0].size(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (i * j) { matrix[i][j] += matrix[i - 1][j] > matrix[i][j - 1] ? matrix[i][j - 1] : matrix[i - 1][j]; } else { if (i > 0) matrix[i][j] += matrix[i - 1][j]; if (j > 0) matrix[i][j] += matrix[i][j - 1]; } } } return matrix[n - 1][m - 1]; } };