✅DFS + DP || ✍️Easy Commented Code
DO UPVOTE If you find it useful !\n\n\n# Intuition\nThe given code solves the problem of finding the maximum number of moves that can be performed in a grid. Th
### DO UPVOTE If you find it useful !\n\n\n# Intuition\nThe given code solves the problem of finding the maximum number of moves that can be performed in a grid. The grid is represented by a 2D matrix with positive integers. The goal is to start at any cell in the first column and traverse the grid, moving to cells where the value is strictly larger than the current cell.\n\n# Approach\n- Initialize a vector row with the values {-1, 0, 1}. This vector represents the row offsets for the three possible moves in each step.\n- Implement a depth-first search (DFS) function dfs that takes the grid, the current row and column, the value of the previous cell, and a DP table dp as input.\n- Check if the result for the current cell is already calculated by looking it up in the DP table. If it is available, return the result.\n- Initialize a variable maxi to 0 to keep track of the maximum number of moves.\n- Iterate over the three possible moves (up, same row, down) and calculate the new row (nr) and column (nc) based on the move.\nCheck if the move is valid by ensuring that the new row and column are within the grid boundaries.\n- Check if the value of the new cell is strictly greater than the previous cell. If it is, calculate the number of moves from this new cell by recursively calling the dfs function with the new row, new column, and new cell value as arguments. Increment the result by 1 to account for the current move\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> row = {-1, 0, 1};\n    \n    // Depth-first search function to find the maximum number of moves\n    int dfs(vector<vector<int>>& grid, int r, int c, int prev, vector<vector<int>>& dp) {\n        int n = grid.size();\n        int m = grid[0].size();\n        int maxi = 0;\n        \n        // Check if the result for the current cell is already calculated\n        if (dp[r][c] != -1) {\n            return dp[r][c];\n        }\n        \n        // Explore all possible moves from the current cell\n        for (int i = 0; i < 3; i++) {\n            int nr = r + row[i];\n            int nc = c + 1;\n            int val = 0;\n            \n            // Check if the move is valid and the value of the cell is strictly greater than the previous cell\n            if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] > prev) {\n                val = 1 + dfs(grid, nr, nc, grid[nr][nc], dp);\n                maxi = max(maxi, val);\n            }\n        }\n        \n        // Store the result for the current cell in the DP table\n        return dp[r][c] = maxi;\n    }\n    \n    int maxMoves(vector<vector<int>>& grid) {\n        int n = grid.size();\n        int m = grid[0].size();\n        int ans = 0;\n        \n        // Initialize the DP table with -1\n        vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));\n        \n        // Iterate over each cell in the first column and find the maximum number of moves\n        for (int i = 0; i < n; i++) {\n            ans = max(ans, dfs(grid, i, 0, grid[i][0], dp));\n        }\n        \n        return ans;\n    }\n};\n\n```
['Dynamic Programming', 'Depth-First Search', 'C++']