Easy DP | Memoization | Trying all below and right cells | Solution in c++
Intuition\nAs you can see option that you can move at any right cell or below cell and to try all possible ways use Dynamic Programming.\n\n# Approach\nThe key 
# Intuition\nAs you can see option that you can move at any right cell or below cell and to try all possible ways use Dynamic Programming.\n\n# Approach\nThe key part is to understand that in you main function you are trying for all below cells and right cells but only you consider further values from function that right and below cell if it\'s positive.As below code is telling that you do move to below cell but consider that cell value as t only if it\'s positive because then it will make sense to take it other do one move and stop as we want to do atleast one move.Same you can do for all right cells.\n\n```\nint t=f(r,j,g);\nif(t>0)\n        ans=max(ans,-g[i][j]+g[r][j]+t);\n        else\n        ans=max(ans,-g[i][j]+g[r][j]);\n```\n\n\n\nAnother point it that the right most and bottom most cell will not be choosen as starting point because you can make any move starting from this cell.That\'s why in below code I have neglected that cell as starting point.\n\n    for(int i=0;i<m;++i)\n        {\n            for(int j=0;j<n;++j)\n            {\n                if(!(i==m-1 && j==n-1))\n                {\n                      maxi=max(maxi,f(i,j,g)); \n                }\n                \n            }\n        }\n\n\nNow understand base condition that why when someone reaches i==m-1 and j==n-1 you have to return 0 because no further value can be gained and every cell can be reachable to that last cell by doing some moves.\n\nNow time complexity is actually $$O(n*m)$$ beacause let\'s say you call first cell i==0 and j==0 so it will call all the function it\'s right side and down which will be get memoized by dp array so further when I will call that cell as starting point it will return from dp array you can tell time complexity as $$O(2*n*m)$$\n# Complexity\n- Time complexity:\n$$O(2*n*m)$$\n\n- Space complexity:\n$$O(n*m)$$ \n\n# Code\n```\nint dp[1001][1001];\n\nint f(int i,int j,vector<vector<int>>& g)\n{\n    if(dp[i][j]!=-1) return dp[i][j];\n    int m=g.size();\n    int n=g[0].size();\n    if(i==m-1 && j==n-1) return dp[i][j]=0;\n    int ans=-1e9;\n    for(int r=i+1;r<m;++r)\n    {\n        int t=f(r,j,g);\n        if(t>0)\n        ans=max(ans,-g[i][j]+g[r][j]+t);\n        else\n        ans=max(ans,-g[i][j]+g[r][j]);\n            \n    }\n    for(int c=j+1;c<n;++c)\n    {\n        int t=f(i,c,g);\n        if(t>0)\n        ans=max(ans,-g[i][j]+g[i][c]+t);\n        else\n        ans=max(ans,-g[i][j]+g[i][c]);\n    }\n    \n    return dp[i][j]=ans;\n}\n\n\nclass Solution {\npublic:\n    int maxScore(vector<vector<int>>& g) {\n        memset(dp,-1,sizeof(dp));\n            int m=g.size();\n    int n=g[0].size();\n        int maxi=-1e9;\n        for(int i=0;i<m;++i)\n        {\n            for(int j=0;j<n;++j)\n            {\n                if(!(i==m-1 && j==n-1))\n                {\n                      maxi=max(maxi,f(i,j,g)); \n                }\n                \n            }\n        }\n        \n        return maxi;\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'Matrix', 'C++']