题解 | #矩阵的最小路径和-斜向遍历法#

递归式

// f(i, j) = min(f(i-1, j) + a[i, j],
//               f(i, j-1) + a[i, j])
// f(0, 0) = a[0, 0]

直接按行或按列遍历，上面和左边的值，可能不存在。

斜向遍历就好了 :)

int minPathSum(vector<vector<int> >& matrix) {
  int m = matrix.size(), n = matrix[0].size();
  vector<vector<int>> f(m, vector<int>(n, 0));
  f[0][0] = matrix[0][0];
  int max_layer = m + n - 2;
  int layer = 0; // 斜向遍历，层数
  while (++layer <= max_layer) {
    for (int i = 0; i <= layer; ++i) {
      int j = layer - i;
      if (i < m && j < n) {
        int from_up = (i-1 >= 0) ? f[i-1][j] : INT_MAX;
        int from_left = (j-1 >= 0) ? f[i][j-1] : INT_MAX;
        f[i][j] = min(from_up, from_left) + matrix[i][j];
      }
    }
  }
  return f[m-1][n-1];
}