Simple Solution Using Memoisation Using C++
Intuition\n Describe your first thoughts on how to solve this problem. \nSimply put we have to find the maximum, we can look for 3 places that is right ,down-ri
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSimply put we have to find the maximum, we can look for 3 places that is right ,down-right, up-right and return the count of the larger elements from this 3 positions so we will simply check this and we can start from any column that is why we have to use a for loop to traverse from every value in the first column and call the function from that value and simply return it.\n\nThe intuition behind using DP is that we have subproblems as at every element we have to check those 3 directions therefore we can use recursion to solve this problem and then memoise it\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe will create a helper function with base conditions such that it does not goes out of bounds \n\nWe will first look at the right side if and only if it is within boundaries and the right side element is greater than the current element, Same would be for down-right and up-right we will first check whether it is inside the boundaries and then whether the current element is smaller than the next element \n\nWe will use a count variable which will track the maximum of the count and the result we got after taking a particular route.\n\nAs the problem stated as we start from any element in the column therefore we will use a for loop to go through every column element and call the function from there and use a maxi to track the maximum element of every function call.\n\nThen we will memoise by caching the output of every result of recursion\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(m * n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(m * n)\n\n# Code\n```cpp []\nclass Solution {\n    private:\n    int h(int i,int j,  vector<vector<int>>&grid, vector<vector<int>>& dp){\n        if(i < 0 || i >= grid.size() || j >= grid[0].size())\n        return 0;\n        int count = 0;\n\n        if (dp[i][j] != -1)  \n            return dp[i][j];\n\n        if(j < grid[0].size() - 1 && grid[i][j + 1] > grid[i][j])\n        count = max(count, h(i, j + 1, grid, dp) + 1);\n        if(i < grid.size() - 1 && j < grid[0].size() - 1 && grid[i + 1][j + 1] > grid[i][j])\n        count = max(count, h(i + 1, j + 1, grid, dp) + 1);\n        if(i > 0 && j < grid[0].size() - 1 && grid[i - 1][j + 1] > grid[i][j])\n        count = max(count, h(i - 1, j + 1, grid, dp) + 1);\n\n        return dp[i][j] = count;\n    }\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        int maxi = 0;\n        vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size(), -1));\n        for(int i = 0;i < grid.size();i++){\n            maxi = max(maxi, h(i, 0, grid, dp));\n        }\n\n        return maxi;\n    }\n};\n```
['C++']