Easy to understand Step by Step Solution | C++ | DP
Intuition\n Describe your first thoughts on how to solve this problem. \nDynamic Programming to reduce repetation in code flow.\n\n# Approach\n Describe your ap
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nDynamic Programming to reduce repetation in code flow.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSolve the problem by storing maximum possible score at each square in grid, starting from the bottom-rightmost square.\nI manually initialised the dp to get clearer idea of the code flow.\n\n# Complexity\n- Time complexity: $$O(m*n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(m*n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        int m = grid.size(), n = grid[0].size();\n        vector<vector<int>> dp( m , vector<int> (n));  \n        // corner\n        dp[m-1][n-1] = INT_MIN;\n        // last row\n        int addR, valR, addB, valB, ans = INT_MIN;\n        for (int i = n-2; i >= 0; i--) {\n            valR = grid[m-1][i+1] - grid[m-1][i];\n            if (dp[m-1][i+1] != INT_MIN) addR = dp[m-1][i+1] + valR;\n            else addR = valR;\n            dp[m-1][i] = max(valR, addR);\n            ans = max(ans, dp[m-1][i]);\n        }\n        // last column\n        for (int i = m-2; i >= 0; i--) {\n            valB = grid[i+1][n-1] - grid[i][n-1];\n            if (dp[i+1][n-1] != INT_MIN) addB = dp[i+1][n-1] + valB;\n            else addB = valB;\n            dp[i][n-1] = max(valB, addB);\n            ans = max(ans, dp[i][n-1]);\n        }\n        // others\n        int Rmax, Bmax;\n        for (int i = m-2; i >= 0; i--) {\n            for (int j = n-2; j >= 0; j--) {\n                valR = grid[i][j+1] - grid[i][j];\n                if (dp[i][j+1] != INT_MIN) addR = dp[i][j+1] + valR;\n                else addR = valR;\n                Rmax = max(valR, addR);\n                \n                valB = grid[i+1][j] - grid[i][j];\n                if (dp[i+1][j] != INT_MIN) addB = dp[i+1][j] + valB;\n                else addB = valB;\n                Bmax = max(valB, addB);\n                \n                dp[i][j] = max(Rmax, Bmax);\n                ans = max(ans, dp[i][j]);\n            }\n        }\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'C++']