Simple DP Recursion + Memoization || Easy to Understand for Beginners
\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nSo, approach will be, we will traverse column 0 by running loop from 0 to n and fo
\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n**So, approach will be, we will traverse column 0 by running loop from 0 to n and for every loop we will recursively call for (i+1, j+1), (i, j+1), (i-1, j+1) and at the end we will take maximum of all and return the ans.\n\nplease upvote if you liked it**\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(N^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N^2)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int f(int i, int j, vector<vector<int>>& grid, vector<vector<int>>& dp) {\n        if (i<0 || i==grid.size() || j==grid[0].size()) return 0;\n\n        if (dp[i][j]!=-1) return dp[i][j];\n\n        int a=0, b=0, c=0;\n\n        if (i+1<grid.size() && j+1<grid[0].size() && grid[i][j]<grid[i+1][j+1]) {\n            a=1+f(i+1, j+1, grid, dp);\n        } \n        if (i<grid.size() && j+1<grid[0].size() && grid[i][j]<grid[i][j+1]) {\n            b=1+f(i, j+1, grid, dp);\n        }\n        if (i-1>=0 && j+1<grid[0].size() && grid[i][j]<grid[i-1][j+1]) {\n            c=1+f(i-1, j+1, grid, dp);\n        }\n\n        return dp[i][j]=max({a, b, c});\n    }\n    int maxMoves(vector<vector<int>>& grid) {\n        int n=grid.size();\n        int m=grid[0].size();\n\n        vector<vector<int>> dp(n, vector<int> (m, -1));\n\n        int ans=0;\n\n        for (int i=0; i<n; i++) {\n            ans=max(ans, f(i, 0, grid, dp));\n        }\n\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'C++']