Re: [閒聊] 每日leetcode

[dont (dont)]

1140. Stone Game II

## 思路

dp(player, i, m)
如果當前player是Alice 就取max, 是Bob 就取min

## Code

```python
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        ALICE, BOB = 0, 1
        n = len(piles)

        @cache
        def dp(p, i, m):
            if i == n:
                return 0

            res = float('-inf') if p == ALICE else float('inf')

            if p == ALICE:
                curr = 0
                for j in range(min(2*m, n-i)):
                    curr += piles[i+j]
                    res = max(res, curr + dp(BOB, i+j+1, max(m, j+1)))
            else:
                for j in range(min(2*m, n-i)):
                    res = min(res, dp(ALICE, i+j+1, max(m, j+1)))

            return res

        return dp(ALICE, 0, 1)
```

補個 用前面大大的解法寫的解

不管player, 就看piles[i:]取1~m個 可以拿到的最大值

dp(i, m) = max(suffix_sum[i] - dp(i+x, max(x,m)))

```
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)

        suffix = [0] * n
        suffix[-1] = piles[-1]
        for i in range(n-2, -1, -1):
            suffix[i] = suffix[i+1] + piles[i]

        @cache
        def dp(i, m):
            if i == n:
                return 0

            if n - i <= 2 * m:
                return suffix[i]

            res = 0
            for j in range(1, 1 + 2 * m):
                res = max(res, suffix[i] - dp(i+j, max(j, m)))
            return res

        return dp(0, 1)
　```

--
http://i.imgur.com/OLvBn3b.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.35.11.142 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724163152.A.719.html
推 CanIndulgeMe: 技術大神
※ 編輯: dont (218.35.11.142 臺灣), 08/20/2024 22:39:58
推 JerryChungYC: 不會dp