C++ | beats 66% | DP - Tabulation
Approachuse recurrence
dp[i][j] = max(max(grid[i + 1][j], grid[i][j + 1]) -
grid[i][j] // 1 move
,
max(dp[i + 1][j] + grid[i + 1][j] - grid[i][j],
dp[i][j + 1]
# Approach
<!-- Describe your approach to solving the problem. -->

use recurrence
dp[i][j] = max(max(grid[i + 1][j], grid[i][j + 1]) -
                                   grid[i][j] // 1 move
                               ,
                               max(dp[i + 1][j] + grid[i + 1][j] - grid[i][j],
                                   dp[i][j + 1] + grid[i][j + 1] - grid[i][j]));

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$O(n*m)$$

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(n*m)$$

# Code
```cpp []
class Solution {
public:
    int maxScore(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, -1e9));

        // a[i][n-1]
        for (int i = m - 2; i >= 0; i--)
            dp[i][n - 1] =
                max(dp[i][n - 1], max(grid[i + 1][n - 1] - grid[i][n - 1],
                                      dp[i + 1][n - 1] + grid[i + 1][n - 1] -
                                          grid[i][n - 1]));

        // a[m-1][j]
        for (int j = n - 2; j >= 0; j--)
            dp[m - 1][j] =
                max(dp[m - 1][j], max(grid[m - 1][j + 1] - grid[m - 1][j],
                                      dp[m - 1][j + 1] + grid[m - 1][j + 1] -
                                          grid[m - 1][j]));

        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                dp[i][j] = max(max(grid[i + 1][j], grid[i][j + 1]) -
                                   grid[i][j] // 1 move
                               ,
                               max(dp[i + 1][j] + grid[i + 1][j] - grid[i][j],
                                   dp[i][j + 1] + grid[i][j + 1] - grid[i][j]));
            }
        }

        int ans = -1e9;
        for (auto& x : dp)
            for (auto& y : x)
                ans = max(y, ans);

        return ans;
    }
};
```
['Array', 'Dynamic Programming', 'Matrix', 'C++']