Leetcode: 1563. Stone Game V
Check out the problem statement here.
Slow Dynamic Programming
Be \(s(i,j)\) the sum of stone values from \(i\) to \(j\), and be \(f(i, j)\) the max score Alice can obtain using stones \(i..j\). When \(i=j\), the game has finished and the score is 0. Otherwise, \(i
With \(n\) being the number of stones, we have that
from functools import cache
from itertools import accumulate
from typing import List
def solve(a):
ps = list(accumulate(a))
def sum(s, e):
return ps[e] - ps[s - 1] if s > 0 else ps[e]
@cache
def rec(s, e):
if s == e:
return 0
ans = 0
for m in range(s + 1, e + 1):
l = sum(s, m - 1)
r = sum(m, e)
if l > r:
ans = max(ans, r + rec(m, e))
elif r > l:
ans = max(ans, l + rec(s, m - 1))
else:
ans = max(
ans,
r + rec(m, e),
l + rec(s, m - 1)
)
return ans
return rec(0, len(ps) - 1)
assert solve([6,2,3,4,5,5]) == 18
assert solve([7,7,7,7,7,7,7]) == 28
assert solve([4]) == 0
class Solution:
def stoneGameV(self, stoneValue: List[int]) -> int:
return solve(stoneValue)
assert Solution().stoneGameV([6,2,3,4,5,5]) == 18
Dynamic Programming on multiple optimizations
To speed up the solution above, we have to avoid checking all possible intervals when computing \(f(i,j)\). But, how could we do that? Is the cubic solution using all constraints of the problem? The answer is "No! The cubic solution is not using the fact that stone values are integers greater than 0". How does this constraint help us when deciding where to split an interval? Let's take \([1, 2, 1, 1, 1, 1]\) as example and \(i=0\) (first stone) and \(j=5\) (last stone). These are all ways to split on an index \(k\):
| k | Left interval sum | Right Interval sum |
| \(s(i,k-1)\) | \(s(k, j)\) | |
| 1 | 1 | 6 |
| 2 | 3 | 4 |
| 3 | 4 | 3 |
| 4 | 5 | 2 |
| 5 | 6 | 1 |
| 6 | 7 | 0 |
Note that for \(k<3\), the left side sum is always smaller than the right side sum. For \(k>=3\), the left side sum is always greater than the right side sum. Such \(k\) will always exist due the constraint of the problem and can be found using a Binary Search. Be \(l(i, j)=\max(s(i,j) + f(i, j), l(i, j - 1))\) for \(i
from functools import cache
from itertools import accumulate
from typing import List
def sum(ps, s, e):
if s > e:
return 0
assert s <= e
assert s >= 0
return ps[e] - ps[s - 1] if s > 0 else ps[e]
def search(ps, a, b):
s, e = a, b
while s <= e:
m = s + (e - s) // 2
l = sum(ps, a, m)
r = sum(ps, m + 1, b)
assert l + r == sum(ps, a, b), (l + r, sum(ps, a, b))
if l >= r:
e = m - 1
else:
s = m + 1
return s
assert search(list(accumulate([1, 1, 1, 1])), 0, 3) == 1
assert search(list(accumulate([1, 1, 3, 1])), 0, 3) == 2
assert search(list(accumulate([4, 1, 1, 1])), 0, 3) == 0
def solve(a):
ps = list(accumulate(a))
@cache
def left(s, e):
if s > e:
return 0
assert s >= 0
assert e < len(a)
return max(sum(ps, s, e) + rec(s, e), left(s, e - 1))
@cache
def right(s, e):
if s > e:
return 0
assert s >= 0
assert e < len(a)
return max(sum(ps, s, e) + rec(s, e), right(s + 1, e))
@cache
def rec(s, e):
if s == e:
return 0
m = search(ps, s, e)
l = sum(ps, s, m)
r = sum(ps, m + 1, e)
ans = 0
if l == r:
return max(left(s, m), right(m + 1, e))
else:
return max(left(s, m - 1), right(m + 1, e))
return ans
return rec(0, len(ps) - 1)
assert solve([6,2,3,4,5,5]) == 18, solve([6,2,3,4,5,5])
assert solve([7,7,7,7,7,7,7]) == 28
assert solve([4]) == 0
class Solution:
def stoneGameV(self, stoneValue: List[int]) -> int:
return solve(stoneValue)
assert Solution().stoneGameV([6,2,3,4,5,5]) == 18