[C++/Java/Python] Minimax, Top down, Bottom up DP - Clean & Concise
Approach 1: Minimax Algorithm\nIdea\n- Let\'s Alice be a maxPlayer and Bob be a minPlayer. On each turn, we need to maximize score of the maxPlayer and minimize
**Approach 1: Minimax Algorithm**\n**Idea**\n- Let\'s `Alice` be a `maxPlayer` and `Bob` be a `minPlayer`. On each turn, we need to maximize score of the `maxPlayer` and minimize score of the `minPlayer`. After all, the final score is the difference in Alice and Bob\'s score if they both play optimally.\n- More about detail Minimax: https://en.wikipedia.org/wiki/Minimax\n\n**Simillar problem**\n- [1406. Stone Game III](https://leetcode.com/problems/stone-game-iii/discuss/564896)\n\n<iframe src="https://leetcode.com/playground/XXxTroDy/shared" frameBorder="0" width="100%" height="550"></iframe>\n\n**Complexity**\n- Time: `O(4*n^2)` ~ `O(n^2)`\n- Space: `O(2 * n^2)` ~ `O(n^2)`\n\n\n**Approach 2: Optimized Top down DP**\n**Idea**\n- There is another way of thinking about this problem.\n- Since both Alice and Bob play optimally, they are trying to maximize their score.\n\t- Alice is trying to maximize her score so that she has a maximum difference from Bob\'s score. \n\t- Bob is also trying to maximize his score so that he is as close to Alice as possible.\n- Our goal is to return the maximum difference in score between Alice and Bob where Alice go first.\n- The difference in score between Alice and Bob can be given by:\n\t- If the current player is Alice: `Difference = Current Score - Difference returned by Bob`\n\t- If the current player is Bob: `Difference = Current Score - Difference returned by Alice`\n- Now, both players have a common goal, that is, to return maximum difference in score to the opponent. We don\'t care who is the current player.\n- Let `dp(left, right)` is the maximum different between the current player and their opponent.\n- We have:\n\t```\n\tdp(left, right) = max(\n\t\tscoreRemoveLeftMost - dp(left+1, right), // case remove left most stone\n\t\tscoreRemoveRightMost - dp(left, right-1) // case remove right most stone\n\t)\n\t```\n- Finally, `dp(0, n-1)` is the maximum difference in score of the whole stones between Alice and Bob, where Alice go first.\n\n<iframe src="https://leetcode.com/playground/WmgNfsoh/shared" frameBorder="0" width="100%" height="500"></iframe>\n\n**Complexity**\n- Time: `O(2*n^2)` ~ `O(n^2)`\n- Space: `O(n^2)`\n\n\n**Appoach 3: Bottom up DP**\n- Exactly same idea with approach 2, just convert Top-down DP into Bottom-up DP.\n<iframe src="https://leetcode.com/playground/CJfwSFVv/shared" frameBorder="0" width="100%" height="480"></iframe>\n\n**Complexity**\n- Time: `O(n^2)`\n- Space: `O(n^2)`
[]