Re: [閒聊] 每日leetcode
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
推
08/20 22:13,
1年前
, 1F
08/20 22:13, 1F
※ 編輯: dont (218.35.11.142 臺灣), 08/20/2024 22:39:58
推
08/21 00:12,
1年前
, 2F
08/21 00:12, 2F
討論串 (同標題文章)
完整討論串 (本文為第 743 之 1548 篇)：