Dynamic Programming  ---  C++
Intuition\nOptimal Substructure - Dynamic Programming (DP)\n\n# Approach\nDP (bottom up)\n\nGiven grid[i][j] as a matrix, starting from any cell at $(i, j)$, le
# Intuition\nOptimal Substructure - Dynamic Programming (DP)\n\n# Approach\nDP (bottom up)\n\nGiven `grid[i][j]` as a matrix, starting from any cell at $(i, j)$, let `dp[i][j]` cache the maximum score attainable.  We need to consider all other cells $(i\', j\')$ if any, with $i\'> i, j\'=j$ (downwards) and $i\'=i, j\'>j$ (to the right), to optimize the score as follows.\n\n`dp[i][j] = max( grid[i\'][j\'] - grid[i][j] + max(dp[i\'][j\'], 0) )`\n\nWithin the outer `max`, the first two terms correspond to the score of moving from $(i,j)$ to $(i\', j\')$, and the inner `max` prevent further moves starting from $(i\',j\')$, if doing so only generates a negative score at the best.\n\nRegroup the terms:\n`dp[i][j] = max( grid[i\'][j\'] + max(dp[i\'][j\'], 0) ) - grid[i][j]`,\nwhere `grid[i][j]` is extracted out of the outer `max`, as it does not depend on $i\'$ or $j\'$.  \n\nWe may use an `aux` matrix to cache the maxima, `max( grid[i\'][j\'] + max(dp[i\'][j\'], 0) )`, for each cell, by considering all available cells downwards or rightwards.  It serves to improve time complexity, and is updated each time we compute a maximal score for a new cell.\n\n# Complexity\n- Time complexity:\nO(m*n)\n\n- Space complexity:\nO(m*n)\n\n# Code\n```\nclass Solution {\npublic:\n    Solution() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);}\n\n    int maxScore(vector<vector<int>>& grid) {\n        const int m = grid.size();\n        const int n = grid[0].size();\n        vector<vector<int>> dp(m, vector<int>(n, 0));\n        vector<vector<int>> aux(m, vector<int>(n, 0));\n        aux[m-1][n-1] = grid[m-1][n-1];\n        int ans{INT_MIN};\n        for (int i = m-2; i >= 0; --i) {\n            dp[i][n-1] = aux[i+1][n-1] - grid[i][n-1];\n            aux[i][n-1] = max(aux[i+1][n-1], grid[i][n-1] + max(dp[i][n-1], 0));\n            ans = max(ans, dp[i][n-1]);\n        }\n        for (int j = n-2; j >= 0; --j) {\n            dp[m-1][j] = aux[m-1][j+1] - grid[m-1][j];\n            aux[m-1][j] = max(aux[m-1][j+1], grid[m-1][j] + max(dp[m-1][j], 0));\n            ans = max(ans, dp[m-1][j]);\n        }\n        for (int i = m-2; i >= 0; --i) {\n            for (int j = n-2; j >= 0; --j) {\n                dp[i][j] = max(aux[i][j+1], aux[i+1][j]) - grid[i][j];\n                aux[i][j] = max({aux[i][j+1], aux[i+1][j], grid[i][j] + max(dp[i][j], 0)});\n                ans = max(ans, dp[i][j]);\n            }\n        }\n        return ans;\n    }\n};\n```
['C++']