Maximum Number of Moves in a Grid

Problem

You are given a 0-indexed m x n matrix grid consisting of positive integers.

You can start at any cell in the first column of the matrix, and traverse the grid in the following way:

From a cell (row, col), you can move to any of the cells: (row - 1, col + 1), (row, col + 1) and (row + 1, col + 1) such that the value of the cell you move to, should be strictly bigger than the value of the current cell.

Return **the *maximum* number of moves that you can perform.**

Example 1:

Input: grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
Output: 3
Explanation: We can start at the cell (0, 0) and make the following moves:
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3).
It can be shown that it is the maximum number of moves that can be made.

Example 2:


Input: grid = [[3,2,4],[2,1,9],[1,1,7]]
Output: 0
Explanation: Starting from any cell in the first column we cannot perform any moves.

Constraints:

m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 105
1 <= grid[i][j] <= 106

Solution (Java)

class Solution {
  int[][] dp;
  int[] dirs = new int[] {-1, 0, 1};
  int m, n, max = 0;

  private int maxMoves(int[][] grid, int x, int y) {
    if (y == n-1) return 0;

    if (dp[x][y] != -1) return dp[x][y];

    dp[x][y] = 0;
    for (var dir : dirs) {
      var x2 = x + dir;
      if (x2 < 0 || x2 == m) continue;

      if (grid[x2][y+1] > grid[x][y])
        dp[x][y] = Math.max(dp[x][y], 1 + maxMoves(grid, x2, y+1));
    }
    return dp[x][y];
  }

  public int maxMoves(int[][] grid) {
    m = grid.length;
    n = grid[0].length;

    dp = new int[m][n];
    for (var row : dp)
      Arrays.fill(row, -1);

    for (var i=0; i<m; i++)
      max = Math.max(max, maxMoves(grid, i, 0));

    return max;
  }
}

Explain:

nope.

Complexity:

Time complexity : O(n).
Space complexity : O(n).