Maximum Number of Moves in a Grid | Leetcode 2684

class Solution {
    int maxMoves(int r,int c,vector<vector<int>>& grid,vector<vector<int>>& mem){
        if(mem[r][c]!=-1)       return mem[r][c];

        int max_moves=0;
        if(r-1>=0 and c+1<grid[0].size() and grid[r-1][c+1]>grid[r][c])
            max_moves = 1 + maxMoves(r-1,c+1,grid,mem);
        if(c+1<grid[0].size() and grid[r][c+1]>grid[r][c])
            max_moves = max(max_moves, 1 + maxMoves(r,c+1,grid,mem));
        if(r+1<grid.size() and c+1<grid[0].size() and grid[r+1][c+1]>grid[r][c])
            max_moves = max(max_moves, 1 + maxMoves(r+1,c+1,grid,mem));
        
        return mem[r][c]=max_moves;
    }
public:
    int maxMoves(vector<vector<int>>& grid) {
        int r=grid.size();
        int c=grid[0].size();

        vector<vector<int>> mem(r,vector<int>(c,-1));
        int max_moves = 0;
        for(int i=0;i<r;++i)
            max_moves = max(max_moves, maxMoves(i,0,grid,mem));
        
        return max_moves;
    }
};

/*
//JAVA
class Solution {
    private int maxMoves(int r, int c, int[][] grid, int[][] mem) {
        if (mem[r][c] != -1) return mem[r][c];

        int maxMoves = 0;
        if (r - 1 >= 0 && c + 1 < grid[0].length && grid[r - 1][c + 1] > grid[r][c]) {
            maxMoves = 1 + maxMoves(r - 1, c + 1, grid, mem);
        }
        if (c + 1 < grid[0].length && grid[r][c + 1] > grid[r][c]) {
            maxMoves = Math.max(maxMoves, 1 + maxMoves(r, c + 1, grid, mem));
        }
        if (r + 1 < grid.length && c + 1 < grid[0].length && grid[r + 1][c + 1] > grid[r][c]) {
            maxMoves = Math.max(maxMoves, 1 + maxMoves(r + 1, c + 1, grid, mem));
        }
        
        mem[r][c] = maxMoves;
        return maxMoves;
    }
    
    public int maxMoves(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;

        int[][] mem = new int[rows][cols];
        for (int[] row : mem) {
            Arrays.fill(row, -1);
        }

        int maxMoves = 0;
        for (int i = 0; i < rows; ++i) {
            maxMoves = Math.max(maxMoves, maxMoves(i, 0, grid, mem));
        }
        
        return maxMoves;
    }
}

#Python
from typing import List

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        def dfs(r, c, grid, mem):
            if mem[r][c] != -1:
                return mem[r][c]

            max_moves = 0
            if r - 1 >= 0 and c + 1 < len(grid[0]) and grid[r - 1][c + 1] > grid[r][c]:
                max_moves = 1 + dfs(r - 1, c + 1, grid, mem)
            if c + 1 < len(grid[0]) and grid[r][c + 1] > grid[r][c]:
                max_moves = max(max_moves, 1 + dfs(r, c + 1, grid, mem))
            if r + 1 < len(grid) and c + 1 < len(grid[0]) and grid[r + 1][c + 1] > grid[r][c]:
                max_moves = max(max_moves, 1 + dfs(r + 1, c + 1, grid, mem))
            
            mem[r][c] = max_moves
            return max_moves

        rows = len(grid)
        cols = len(grid[0])
        mem = [[-1] * cols for _ in range(rows)]

        max_moves = 0
        for i in range(rows):
            max_moves = max(max_moves, dfs(i, 0, grid, mem))
        
        return max_moves

*/