Memoized Version of Lee's Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nFor those whose intuition works by recursion and memoization, this solution is the simp
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFor those whose intuition works by recursion and memoization, this solution is the simplest way to solve this problem.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nLee\'s solution explains the intuition as follows,\n1. Maintain the top-left min value among the elements. Note that, this problem boils down to one start and end point as in-between cancels out everything. Note this is not the answer,\n2. Maintain a max element of (c2-c1) i.e., for each element checks its subtraction to a memoized min so far for it\'s top-left. This would be the final answer as max can occur anywhere in-between.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N^2)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N^2). Note we can use the same input array in memoization and reduce it to O(1)\n\n# Code\n```\nclass Solution {\n    int res=-1e6;\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        vector<vector<int>> m(grid.size(),vector<int>(grid[0].size(),-1e6));\n        dp(grid.size()-1,grid[0].size()-1,grid,m);\n        return res;\n    }\n    //https://leetcode.com/problems/maximum-difference-score-in-a-grid/solutions/5145704/java-c-python-dp-minimum-on-top-left/\n    int dp(int i,int j,vector<vector<int>>& grid,vector<vector<int>>& memo){\n        if(i<0||j<0){\n            return 1e6;\n        }\n        //cout<<i<<" "<<j<<endl;\n        if(memo[i][j]!=-1e6){\n            return memo[i][j];\n        }\n        int pre=min(dp(i-1,j,grid,memo),dp(i,j-1,grid,memo));\n        res=max(res,grid[i][j]-pre);\n        return memo[i][j]=min(grid[i][j],pre);\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']