// 64. Minimum Path Sum
int minPathSum(vector<vector<int>>& grid) {
  if (!grid.size() || !grid[0].size()) return 0;
  int row = grid.size();
  int col = grid[0].size();
  vector<int> last_record(col, INT_MAX);
  last_record[0] = 0;
  for (int r = 0; r < row; ++r) {
    last_record[0] += grid[r][0];
    for (int c = 1; c < col; ++c) {
      last_record[c] = min(last_record[c], last_record[c-1]) + grid[r][c];
    }
  }
  return last_record[col-1];
}

// 62. Unique Paths
int uniquePaths(int m, int n) {
  if (m <= 0 || n <= 0) return 0;
  int record[100] = {0};
  record[0] = 1;
  for (int r = 0; r < m; ++r) {
    for (int c = 1; c < n; ++c) {
      record[c] += record[c-1];
    }
  }
  return record[n-1];
}

// 63. Unique Paths II
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
  if (!obstacleGrid.size() || !obstacleGrid[0].size()) return 0;
  int row = obstacleGrid.size();
  int col = obstacleGrid[0].size();
  vector<int> record(col, 0);
  record[0] = 1 - obstacleGrid[0][0];
  for (int r = 0; r < row; ++r) {
    record[0] &= 1 - obstacleGrid[r][0];
    for (int c = 1; c < col; ++c) {
      if (obstacleGrid[r][c] > 0) {
        record[c] = 0;
        continue;
      }
      record[c] += record[c - 1];
    }
  }
  return record[col - 1];
}