Brute Force DP with optimised solution with comments and Intution
Brute Force Solution(TLE)\nHere dp[i][j]-> It tells we have maximum score we can get if we consider from (i,j) to (n-1,m-1)\n\nclass Solution {\npublic:\n    us
* Brute Force Solution(TLE)\nHere dp[i][j]-> It tells we have maximum score we can get if we consider from (i,j) to (n-1,m-1)\n```\nclass Solution {\npublic:\n    using v1d = vector<int>;\n    using v2d = vector<v1d>;\n    int maxScore(vector<vector<int>>& grid) {\n        int n=grid.size(),m=grid[0].size();\n        v2d dp(n,v1d(m,-1e9));\n        for(int i=n-1;i>=0;i--){\n            for(int j=m-1;j>=0;j--){\n                for(int newi=i+1;newi<n;newi++){\n                    dp[i][j]=max(dp[i][j],grid[newi][j]-grid[i][j]);\n                    dp[i][j]=max(dp[i][j],grid[newi][j]-grid[i][j]+dp[newi][j]);\n                }\n                for(int newj=j+1;newj<m;newj++){\n                    dp[i][j]=max(dp[i][j],grid[i][newj]-grid[i][j]);\n                    dp[i][j]=max(dp[i][j],grid[i][newj]-grid[i][j]+dp[i][newj]);\n                }\n            }\n        }\n        int res=-1e9;\n        for(int i=0;i<n;i++){\n            for(int j=0;j<m;j++){\n                res=max(res,dp[i][j]);\n            }\n        }\n        return res;\n    }\n};\n\n```\n\n* Optimised solution using min top-left \n* 1. Observation here: (a-b) + (c-b) + ....... = last element taken - first element taken.\n* All other things cancel out and they are redundant to consider\n```\nclass Solution {\npublic:\n    using v1d = vector<int>;\n    using v2d = vector<v1d>;\n    int maxScore(vector<vector<int>>& grid) {\n        int n=grid.size(),m=grid[0].size();\n        v2d dp(n,v1d(m,1e9));\n        //dp[i][j] -> Minimum element in the top left column\n        //Transition -> Have to update dp[i][j],res\n        int res=-1e9;\n        for(int i=0;i<n;i++){\n            for(int j=0;j<m;j++){\n                if(i>0) dp[i][j]=min(dp[i][j],dp[i-1][j]);\n                if(j>0) dp[i][j]=min(dp[i][j],dp[i][j-1]);\n                res=max(res,grid[i][j]-dp[i][j]);\n                dp[i][j]=min(dp[i][j],grid[i][j]);\n            }\n        }\n        return res;\n    }\n};\n```\n\nThis solution can be further optimides without using extra space of dp. It can be done by using grid as out dp array
['Dynamic Programming', 'C']