C++ Bottom-up DP O(N^2) time
\nSee my latest update in repo LeetCode\n\n## Solution 1. Bottom-up DP\n\nLet dp[i][j] be the maximum difference the first player can get if the players play on
\nSee my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1. Bottom-up DP\n\nLet `dp[i][j]` be the maximum difference the first player can get if the players play on `A[i..j]`.\n\n```\ndp[i][j] = max(\n                sum(i + 1, j) - dp[i + 1][j],   // if the first player choose `A[i]`\n                sum(i, j - 1) - dp[i][j - 1]    // if the first player choose `A[j]`\n              )\n```\nwhere `sum(i, j)` is `A[i] + ... + A[j]`. We can get `sum(i, j)` using prefix sum array.\n\n```cpp\n// OJ: https://leetcode.com/contest/weekly-contest-219/problems/stone-game-vii/\n// Author: github.com/lzl124631x\n// Time: O(N^2)\n// Space: O(N^2)\nclass Solution {\npublic:\n    int stoneGameVII(vector<int>& A) {\n        int N = A.size();\n        vector<int> sum(N + 1);\n        for (int i = 0; i < N; ++i) sum[i + 1] = sum[i] + A[i];\n        vector<vector<int>> dp(N, vector<int>(N));\n        for (int len = 2; len <= N; ++len) {\n            for (int i = 0; i <= N - len; ++i) {\n                int j = i + len - 1;\n                dp[i][j] = max(sum[j + 1] - sum[i + 1] - dp[i + 1][j], sum[j] - sum[i] - dp[i][j - 1]);\n            }\n        }\n        return dp[0][N - 1];\n    }\n};\n```\n\n---\n\nUpdate 1/18/2021:\n\nAdding some explanation.\n\nEach player needs to play optimally to get as many points as possible and make the other player get as less as possible. So the game is actually the same for both of them.\n\nAfter Alice finshes the her first round, ignoring the points Alice made there, the game to Bob is exactly the same as if he is the first player.\n\nSo each round on `A[i..j]`, no matter who plays first, the first player always has two options:\n1. pick `A[i]`, the first player get `sum(i + 1, j)` points, and we need to deduct the maximum point difference the next player can get in the remaining game, i.e. `dp[i + 1][j]`\n2. pick `A[j]`, the first player get `sum(i, j - 1)` points, and we need to deduct the maximum point difference the next player can get in the remaining game, i.e. `dp[i][j - 1]`\n\nAnd the first player simply pick the option more advantageous to him/her.
[]