🔥Easy Explanation | |✅ Simple Solution | | 🧠Beginner friendly
\n# Approach\n1. Since we are allowed to start from any index initiate recursion call from all the indices\n2. For Every Index (i,j) There are 4 Choices.\n- Cho
\n# Approach\n**1**. Since we are allowed to start from any index initiate recursion call from all the indices\n**2**. For Every Index (i,j) There are 4 Choices.\n- **Choice 1**:Move to right index `(i,j+1)` stop the further indices consideration\n- **Choice 2**:Move to right index `(i,j+1)` ,make recursive `(eg. function(i,j+1))` for further indices consideration.\n- **Choice 3**:Move to bottom index `(i+1,j)` stop the further indices consideration\n- **Choice 4**:Move to bottom index `(i+1,j)` ,make recursive `(eg. function(i+1,j))` for further indices consideration.\n**3**. Consider Max of all 4 choices\n# Complexity\n- Time complexity:\n $$O(m*n)$$ \n\n- Space complexity:\n$$O(m*n)$$ \n\n# Code\n```cpp []\nclass Solution {\n    int n,m;\n    int get(int i,int j,vector<vector<int>>& grid,vector<vector<long long>> &dp){\n        if(i>=n || j>=m){\n            return 0;\n        }\n\n        if(dp[i][j]!=LLONG_MAX){\n            return dp[i][j];\n        }\n        long long  right=INT_MIN,bottom=INT_MIN;\n        long long  a=INT_MIN,b=INT_MIN;\n\n        if(j+1<m){\n            a=(grid[i][j+1]-grid[i][j]);//Choice 1\n            right=a+get(i,j+1,grid,dp);//Choice 2\n        }\n        if(i+1<n){\n            b=(grid[i+1][j]-grid[i][j]);//Choice 3\n            bottom=b+get(i+1,j,grid,dp);//Choice 3\n        }\n        return  dp[i][j]=max(a,max(b,max(right,bottom)));\n    }\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        n=grid.size(),m=grid[0].size();\n        int maxi=INT_MIN;\n        vector<vector<long long>> dp(n,vector<long long>(m,LLONG_MAX));\n        \n        for(int i=0;i<n;i++){\n           for(int j=0;j<m;j++){\n             maxi=max(maxi,get(i,j,grid,dp));\n           }\n        }\n        return maxi;\n    }\n};\n```
['Dynamic Programming', 'Backtracking', 'C++']