DFS -> DFS+MEMO -> DP  !~!~
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n# DFS = > TLE\n\n# DFS+
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n# ***DFS*** = > TLE\n![image.png](https://assets.leetcode.com/users/images/928219f0-f854-46a2-88ac-9061b2a7cede_1730267713.192267.png)\n# ***DFS+MEMO*** = > 12ms Beats 82.93%\n![image.png](https://assets.leetcode.com/users/images/f661ceed-f0d8-465c-a358-332b8d9e6cf4_1730267756.422382.png)\n\n# ***DP*** = > 11ms Beats 85.37%\n![image.png](https://assets.leetcode.com/users/images/0dcf23e7-2d7e-422a-9c22-a4fa4f227c2c_1730267743.8401482.png)\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code \nDFS\n```cpp []\n------------------------------------------------------------------\nclass Solution {\npublic:\n    int m,n;\n    int dfs(vector<vector<int>>& grid,int row,int col){\n        if(row<0 || row>=m || col<0 || col >=n){\n            return 0;\n        }\n        int ur=0,r=0,dr=0;\n        if(row-1>=0&&col+1<n&&grid[row][col]<grid[row-1][col+1])ur = dfs(grid,row-1,col+1)+1;\n        if(col+1<n&&grid[row][col]<grid[row][col+1])r = dfs(grid,row,col+1)+1;\n        if(row+1<m&&col+1<n&&grid[row][col]<grid[row+1][col+1])dr = dfs(grid,row+1,col+1)+1;\n        return max({ur,r,dr});\n    }\n    int maxMoves(vector<vector<int>>& grid) {\n        int maxMoves = 0;\n        m = grid.size(),n = grid[0].size();\n        for(int i=0;i<m;i++){\n            maxMoves = max(maxMoves,dfs(grid,i,0));\n        }\n        return maxMoves;\n    }\n};\n```\n\n------------------------------------------------------------------\n DFS+MEMO\n```C++ []\nclass Solution {\npublic:\n    int m,n;\n    vector<vector<int>> memo;\n    int dfs(vector<vector<int>>& grid,int row,int col){\n        if(row<0 || row>=m || col<0 || col >=n){\n            return 0;\n        }\n        if(memo[row][col]!=-1)return memo[row][col];\n        int ur=0,r=0,dr=0;\n        if(row-1>=0&&col+1<n&&grid[row][col]<grid[row-1][col+1])ur = dfs(grid,row-1,col+1)+1;\n        if(col+1<n&&grid[row][col]<grid[row][col+1])r = dfs(grid,row,col+1)+1;\n        if(row+1<m&&col+1<n&&grid[row][col]<grid[row+1][col+1])dr = dfs(grid,row+1,col+1)+1;\n        return memo[row][col] = max({ur,r,dr});\n    }\n    int maxMoves(vector<vector<int>>& grid) {\n        int maxMoves = 0;\n        m = grid.size(),n = grid[0].size();\n        memo.assign(m,vector<int>(n,-1));\n        for(int i=0;i<m;i++){\n            maxMoves = max(maxMoves,dfs(grid,i,0));\n        }\n        return maxMoves;\n    }\n};\n```\n\n\n------------------------------------------------------------------\nDP\n```C++ []\nclass Solution {\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        int maxMoves = 0;\n        int m = grid.size(),n = grid[0].size();\n        vector<vector<int>> dp(m,vector<int>(n,0));\n        \n        for(int i=0;i<n-1;i++){\n            for(int j=0;j<m;j++){\n                if(i!=0 && dp[j][i]==0)continue;\n\n                if(j-1>=0 && grid[j][i]<grid[j-1][i+1]){\n                    dp[j-1][i+1] = max(dp[j-1][i+1],dp[j][i]+1);\n                    maxMoves = max(maxMoves,dp[j-1][i+1]);\n                }\n                if(grid[j][i]<grid[j][i+1]){\n                    dp[j][i+1] = max(dp[j][i+1],dp[j][i]+1);\n                    maxMoves = max(maxMoves,dp[j][i+1]);\n                }\n                if(j+1<=m-1 && grid[j][i]<grid[j+1][i+1]){\n                    dp[j+1][i+1] = max(dp[j+1][i+1],dp[j][i]+1);\n                    maxMoves = max(maxMoves,dp[j+1][i+1]);\n                }\n            }\n        }\n\n        return maxMoves;\n    }\n};\n```
['C++']