Maximum Number of Moves in a Grid

medium graph dp dfs grid

Problem

You are given an m x n grid of positive integers. You can start at any cell in the first column. From a cell (r, c) you may move to (r-1, c+1), (r, c+1), or (r+1, c+1) — that is, one column to the right and at most one row up or down — but only if the destination value is strictly greater than the current cell's value. Return the maximum number of moves you can make.

Think of each cell as a graph node with up to three forward edges into the next column. The longest increasing chain starting at a cell is one plus the best of its reachable neighbours, so a column-by-column DP (filled right to left) gives every cell's best move count; the answer is the largest over the first column.

Input

Output3

Starting at (0,0)=2 → (0,1)=4 → (1,2)=9 → (2,3)=11 makes 3 moves, the maximum possible.

grid (rows by ';', positive ints by space)

def max_moves(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    best = 0
    for c in range(cols - 2, -1, -1):
        for r in range(rows):
            m = 0
            for dr in (-1, 0, 1):
                nr = r + dr
                if 0 <= nr < rows and grid[nr][c + 1] > grid[r][c]:
                    m = max(m, dp[nr][c + 1] + 1)
            dp[r][c] = m
    for r in range(rows):
        best = max(best, dp[r][0])
    return best

function maxMoves(grid) {
  const rows = grid.length, cols = grid[0].length;
  const dp = Array.from({ length: rows }, () => new Array(cols).fill(0));
  let best = 0;
  for (let c = cols - 2; c >= 0; c--) {
    for (let r = 0; r < rows; r++) {
      let m = 0;
      for (const dr of [-1, 0, 1]) {
        const nr = r + dr;
        if (nr >= 0 && nr < rows && grid[nr][c + 1] > grid[r][c]) {
          m = Math.max(m, dp[nr][c + 1] + 1);
        }
      }
      dp[r][c] = m;
    }
  }
  for (let r = 0; r < rows; r++) best = Math.max(best, dp[r][0]);
  return best;
}

class Solution {
    public int maxMoves(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int[][] dp = new int[rows][cols];
        int best = 0;
        for (int c = cols - 2; c >= 0; c--) {
            for (int r = 0; r < rows; r++) {
                int m = 0;
                for (int dr = -1; dr <= 1; dr++) {
                    int nr = r + dr;
                    if (nr >= 0 && nr < rows && grid[nr][c + 1] > grid[r][c]) {
                        m = Math.max(m, dp[nr][c + 1] + 1);
                    }
                }
                dp[r][c] = m;
            }
        }
        for (int r = 0; r < rows; r++) best = Math.max(best, dp[r][0]);
        return best;
    }
}

class Solution {
public:
    int maxMoves(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        vector<vector<int>> dp(rows, vector<int>(cols, 0));
        int best = 0;
        for (int c = cols - 2; c >= 0; c--) {
            for (int r = 0; r < rows; r++) {
                int m = 0;
                for (int dr = -1; dr <= 1; dr++) {
                    int nr = r + dr;
                    if (nr >= 0 && nr < rows && grid[nr][c + 1] > grid[r][c]) {
                        m = max(m, dp[nr][c + 1] + 1);
                    }
                }
                dp[r][c] = m;
            }
        }
        for (int r = 0; r < rows; r++) best = max(best, dp[r][0]);
        return best;
    }
};

Explanation

Every move goes exactly one column to the right and lands on a strictly larger value, so a path can never revisit a column or cycle — the grid behaves like a directed acyclic graph layered by column. That makes it a clean dynamic programming problem.

Define dp[r][c] as the maximum number of moves you can make starting from cell (r, c). Cells in the last column can go nowhere, so their value is 0 — this is the base case.

For any other cell we look at its three forward neighbours in the next column: (r-1, c+1), (r, c+1), (r+1, c+1). For each neighbour that is in bounds and strictly larger, taking it costs one move plus whatever that neighbour can achieve, namely dp[nr][c+1] + 1. We keep the best of these (or 0 if none qualify).

Because each cell depends only on the column to its right, we fill the table right to left. The answer is the maximum dp over the first column, since we may start at any cell there.

Worked example: the chain 2 → 4 → 9 → 11 climbs through columns 0–3 making 3 moves, and the DP confirms no first-column cell can do better, so the answer is 3.

Time: O(m · n) Space: O(m · n)