Maximum Number of Moves in a Grid

export function maxMoves(grid: number[][]): number {
  const [m, n] = [grid.length, grid[0].length];
  const dirs = [
    [-1, 1],
    [0, 1],
    [1, 1],
  ];
 
  function canMove(row: number, col: number) {
    return 0 <= row && row < m && 0 <= col && col < n;
  }
 
  function dfs(row: number, col: number, dp: number[][]): number {
    if (dp[row][col] !== -1) {
      return dp[row][col];
    }
    let maxMoves = 0;
    for (const [drow, dcol] of dirs) {
      const [nrow, ncol] = [row + drow, col + dcol];
      if (canMove(nrow, ncol) && grid[row][col] < grid[nrow][ncol]) {
        maxMoves = Math.max(maxMoves, 1 + dfs(nrow, ncol, dp));
      }
    }
    dp[row][col] = maxMoves;
    return maxMoves;
  }
 
  let answer = 0;
  for (let row = 0; row < m; row++) {
    const dp = Array.from({ length: m }, () => new Array(n).fill(-1));
    answer = Math.max(answer, dfs(row, 0, dp));
  }
  return answer;
}

export function maxMoves(grid: number[][]): number {
  const [m, n] = [grid.length, grid[0].length];
 
  let answer = 0;
  let prev = new Array<number>(m).fill(1);
  for (let col = 1; col < n; col++) {
    const curr = new Array<number>(m).fill(0);
    for (let row = 0; row < m; row++) {
      if (grid[row][col - 1] < grid[row][col] && 0 < prev[row]) {
        curr[row] = Math.max(curr[row], prev[row] + 1);
      }
 
      if (1 <= row && grid[row - 1][col - 1] < grid[row][col] && 0 < prev[row - 1]) {
        curr[row] = Math.max(curr[row], prev[row - 1] + 1);
      }
 
      if (row < m - 1 && grid[row + 1][col - 1] < grid[row][col] && 0 < prev[row + 1]) {
        curr[row] = Math.max(curr[row], prev[row + 1] + 1);
      }
      answer = Math.max(answer, curr[row] - 1);
    }
    prev = curr;
  }
  return answer;
}