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

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];
    }
};