[Python] Top Down and Bottom Up DP - explained
Approach:\n\nEach player is trying to maximize their score so\nwhen Alice picks up a stone[i] she gains the \nremaining points in the array knowing that Bob\nwi
**Approach:**\n\nEach player is trying to maximize their score so\nwhen Alice picks up a stone[i] she gains the \nremaining points in the array knowing that Bob\nwill pick the optimal stone next round.\n\nRather than giving Bob the points, we subtract\nBob\'s points from Alice\'s points.\n\n***think of it like Bob gets negative points and Alice gets\npositive points and the sum of Bob\'s and Alice\'s points\nequals the amount of points Alice will win by***\n\n**Implementation:**\n\nUse two pointers i and j to mark the start and end\nof the remaining stones.  \n\nIf the left stone is picked, increment i by 1 and \nif the right stone is picked increment j by -1.\n\nWhen i == j then there is only one stone to pick from.\nAnd if i > j return 0 because there are no more stones.\n\n\n**Optimizations:**\n\nUse a presum array to calculate the sum of the stones\nremaining in O(1) time.  \n\nThis can be done because ```presum[i]``` tells us\nthe sum of all the stones to the left of i (inclusive).\n\nAnd ```presum[j]``` tells us the sum of all the stones to\nthe left of j (inclusive).\n\nSo ```presum[j] - presum[i-1]``` equals sum(stones[i:j+1]) which is\nthe amount of points from the remaining stoens in the range [i,j].\n\n**Recursive Visualization:**\n\nSay A<sub>N</sub> and B<sub>N</sub> is Alice and Bob\'s score for picking up the N<sup>th</sup> stone.\nThe recursive function will look like this:\n\n```html5\nA<sub>1</sub> - (B<sub>2</sub> - (A<sub>3</sub> - (B<sub>4</sub> - (A<sub>5</sub> - (B<sub>6</sub> - ...)))))\n```\n\nWhich simplifies to:\n\n```html5\nA<sub>1</sub> + A<sub>3</sub> + A<sub>5</sub> + ... - (B<sub>2</sub> + B<sub>4</sub> + B<sub>6</sub> + ...)\n```\n\n<br>\n\n```python\ndef stoneGameVII(self, stones: List[int]) -> int:\n\t\n\tpresum = [0] + stones[:]\n\tfor i in range(1, len(presum)):\n\t\tpresum[i] += presum[i-1]\n\t\t\n\tdef score(i, j):\n\t\tj += 1\n\t\treturn presum[j] - presum[i]\n\t\n\tn = len(stones)\n\tdp = [[0 for _ in range(n)] for _ in range(n)]\n\tfor i in range(n-1, -1, -1):\n\t\tfor j in range(i+1, n):\n\t\t\tdp[i][j] = max(score(i+1, j) - dp[i+1][j], score(i, j-1) - dp[i][j-1])\n\t\n\treturn dp[0][n-1]\n```\n\n<br>\n\n<details>\n\n<summary>Top Down DP: <b>remember to clear the cache</b> (click to show)</summary>\n\n```python\ndef stoneGameVII(self, stones: List[int]) -> int:\n\t\n\tpresum = [0] + stones[:]\n\tfor i in range(1, len(presum)):\n\t\tpresum[i] += presum[i-1]\n\t\t\n\tdef score(i, j):\n\t\tj += 1\n\t\treturn presum[j] - presum[i]\n\t\t\n\t@functools.lru_cache(None)\n\tdef helper(i, j):\n\t\tif i >= j:\n\t\t\treturn 0\n\t\treturn max(score(i+1, j) - helper(i+1, j), score(i, j-1) - helper(i, j-1))\n\n\tres = helper(0, len(stones) - 1)\n\thelper.cache_clear()\n\treturn res\n```\n\n</details>
[]