/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
  let row = grid.length;
  let col = grid[0].length;
  let [x, y] = [0, 0];
  let visited = Array.from(Array(row), () => Array(col).fill(0));
  const next = [
    [0, 1],
    [1, 0],
  ];

  let answer = Infinity;
  const dfs = (x, y, visited, acc) => {
    acc += grid[x][y];
    if (x === row - 1 && y === col - 1) {
      answer = answer > acc ? acc : answer;
      return;
    }
    for (let i = 0; i < 2; i++) {
      let nx = x + next[i][0];
      let ny = y + next[i][1];
      if (nx >= 0 && ny >= 0 && nx < row && ny < col && visited[nx][ny] === 0) {
        visited[x][y] = 1;
        dfs(nx, ny, visited, acc);
        visited[x][y] = 0;
      }
    }
  };

  dfs(x, y, visited, 0);
  return answer;
};

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
  const row = grid.length;
  const col = grid[0].length;
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (i == 0 && j == 0) {
        continue;
      }
      if (i == 0) {
        grid[i][j] = grid[i][j] + grid[i][j - 1];
        continue;
      }
      if (j == 0) {
        grid[i][j] = grid[i][j] + grid[i - 1][j];
        continue;
      }
      grid[i][j] = Math.min(grid[i][j] + grid[i][j - 1], grid[i][j] + grid[i - 1][j]);
    }
  }
  return grid[row - 1][col - 1];
};