Explained - both DP & DFS approach || Very simple & easy to understand solution
Up vote if you like the solution\n\n# Approach \n1. Take one extra space of the size of the grid and initialise all to 0.\n2. Then keep checking from the last s
<b>Up vote if you like the solution</b>\n\n# Approach \n1. Take one extra space of the size of the grid and initialise all to 0.\n2. Then keep checking from the last second column the next three possible node\n   and take the max of them with 1 added to them.\n3. Repeat above for all other nodes and keep traking for max value when the column is 0.\n    \n# Code\n\nApproach - 1: DP with simple iteration\n```\nint maxMoves(vector<vector<int>>& grid) {\n    int ans = 0;\n    vector<vector<int>> dp(grid.size(), vector<int> (grid[0].size(), 0));\n    for(int c = grid[0].size()-2; c >= 0; --c){\n        for(int r = 0; r < grid.size(); ++r ){\n            if(r - 1 >= 0 && grid[r][c] < grid[r-1][c+1])  { \n                dp[r][c] = max(dp[r][c], 1 + dp[r-1][c+1]); \n            }\n            if( grid[r][c] < grid[r][c+1]) { \n                dp[r][c] = max(dp[r][c], 1 + dp[r][c+1]); \n            }\n            if(r + 1 < grid.size() && grid[r][c] < grid[r+1][c+1]) { \n                dp[r][c] = max(dp[r][c], 1 + dp[r+1][c+1]); \n            }\n            if(c == 0) { ans = max(ans, dp[r][c]);  }\n        }\n    }\n    return ans;\n}\n```\n\nApproach - 2: DFS solution \n```\nclass Solution {\npublic:\n    int dfs(vector<vector<int>>& grid, int r, int c, int prev){\n        if(r < 0 || r == grid.size() || c == grid[0].size() || prev >= grid[r][c] ) return 0;\n        prev = grid[r][c];\n        grid[r][c] = INT_MAX;\n        int res = dfs(grid, r-1, c+1, prev);\n        res = max(res, dfs(grid, r, c+1, prev ));\n        res = max(res, dfs(grid, r+1, c+1, prev));\n        return res + 1;\n    }\n    int maxMoves(vector<vector<int>>& grid) {\n        int ans = 0;\n        for(int i = 0; i < grid.size(); ++i) ans = max(ans, dfs(grid, i, 0, 0));\n        return ans-1;\n    }\n};\n```\n\n\n\n<b>Here is an article of my last interview experience - A Journey to FAANG Company, I recomand you to go through this to know which all resources I have used & how I cracked interview at Amazon:\nhttps://leetcode.com/discuss/interview-experience/3171859/Journey-to-a-FAANG-Company-Amazon-or-SDE2-(L5)-or-Bangalore-or-Oct-2022-Accepted
['C++']