[Java] DFS + Memoization based approach
Intuition\n\n\n1. Try to explore DFS path from every single cell in first column\n2. Every cell could have multiple choices to go to. Explore all paths and find
# Intuition\n\n```\n1. Try to explore DFS path from every single cell in first column\n2. Every cell could have multiple choices to go to. Explore all paths and find path from each cell that can lead to maximum number of moves.\n```\n\n# Plain DFS code which gives TLE\n\n```\nclass Solution {\n\n    int[] dx = {-1, 0, 1};\n    int[] dy = {1, 1, 1};\n\n    private boolean isSafe(int[][] grid, int x, int y) {\n        int n = grid.length;\n        int m = grid[0].length;\n\n        if(x<0 || x>=n || y<0 || y>=m) {\n            return false;\n        }\n\n        return true;\n    }\n\n    private int dfs(int[][] grid, int x, int y) {\n        //already pulled a node\n\n        //do the work\n        int moves = 0;\n\n        //explore neighbors\n        int newX = 0, newY = 0;\n        for(int k = 0; k<3; k++) {\n            newX = x + dx[k];\n            newY = y + dy[k];\n\n            if(isSafe(grid, newX, newY) && grid[newX][newY] > grid[x][y]) {\n                moves = Math.max(moves, 1 + dfs(grid, newX, newY));\n            }\n        }\n\n        return moves;\n    }\n\n    public int maxMoves(int[][] grid) {\n        if(grid == null || grid.length == 0) {\n            return 0;\n        }\n\n        int maxMoves = 0;\n\n        int n = grid.length;\n        int m = grid[0].length;\n\n        //try dfs from every single call of first column\n        int maxPathLength = 0;\n        for(int i = 0; i<n; i++) {\n            maxPathLength = dfs(grid, i, 0);\n            maxMoves = Math.max(maxMoves, maxPathLength);\n        }\n\n        return maxMoves;\n    }\n}\n```\n\n# DFS + Memoization\n\n```java []\nclass Solution {\n\n    int[] dx = {-1, 0, 1};\n    int[] dy = {1, 1, 1};\n\n    private boolean isSafe(int[][] grid, int x, int y) {\n        int n = grid.length;\n        int m = grid[0].length;\n\n        if(x<0 || x>=n || y<0 || y>=m) {\n            return false;\n        }\n\n        return true;\n    }\n\n    private int dfs(int[][] grid, int[][] dp, int x, int y) {\n        //already pulled a node\n\n        //do the work\n        if(dp[x][y] != 0) {\n            return dp[x][y];\n        }\n\n        int moves = 0;\n\n        //explore neighbors\n        int newX = 0, newY = 0;\n        for(int k = 0; k<3; k++) {\n            newX = x + dx[k];\n            newY = y + dy[k];\n\n            if(isSafe(grid, newX, newY) && grid[newX][newY] > grid[x][y]) {\n                moves = Math.max(moves, 1 + dfs(grid, dp, newX, newY));\n            }\n        }\n\n        dp[x][y] = moves;\n        return moves;\n    }\n\n    public int maxMoves(int[][] grid) {\n        if(grid == null || grid.length == 0) {\n            return 0;\n        }\n\n        int maxMoves = 0;\n\n        int n = grid.length;\n        int m = grid[0].length;\n\n        //for memoization\n        int[][] dp = new int[n][m];\n\n        //try dfs from every single call of first column\n        int maxPathLength = 0;\n        for(int i = 0; i<n; i++) {\n            maxPathLength = dfs(grid, dp, i, 0);\n            maxMoves = Math.max(maxMoves, maxPathLength);\n        }\n\n        return maxMoves;\n    }\n}\n```
['Java']