Stone Game V — LeetCode 1563 Python Solution
HardArrayMathDynamic ProgrammingGame Theory
- Problem
- #1563
- Pattern
- Dynamic Programming
- Reading time
- 6 min
- Source
- leetcode.com
The problem
There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue. In each round of the game, Alice divides the row into two non-empty rows (i.e.
Example
- Input
- stoneValue = [6,2,3,4,5,5]
- Output
- 18
- Explanation
- In the first round, Alice divides the row to [6,2,3], [4,5,5]. The left row has the value 11 and the right row has value 14. Bob throws away the right row and Alice's score is now 11.
Python solution
Python
def max(a: int, b: int) -> int:
return a if a > b else b
class Solution:
def stoneGameV(self, stoneValue: List[int]) -> int:
@cache
def dfs(i: int, j: int) -> int:
if i >= j:
return 0
ans = l = 0
r = s[j + 1] - s[i]
for k in range(i, j):
l += stoneValue[k]
r -= stoneValue[k]
if l < r:
if ans >= l * 2:
continue
ans = max(ans, l + dfs(i, k))
elif l > r:
if ans >= r * 2:
break
ans = max(ans, r + dfs(k + 1, j))
else:
ans = max(ans, max(l + dfs(i, k), r + dfs(k + 1, j)))
return ans
s = list(accumulate(stoneValue, initial=0))
return dfs(0, len(stoneValue) - 1)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n^3) |
| Space | O(n^2) auxiliary |
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1563. Stone Game V is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1563. Stone Game V?
- LeetCode 1563. Stone Game V is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1563. Stone Game V?
- The Python solution on this page runs in O(n^3).
- What is the space complexity of LeetCode 1563. Stone Game V?
- The Python solution on this page uses O(n^2) auxiliary space.
- What topics does LeetCode 1563. Stone Game V cover?
- LeetCode 1563. Stone Game V is tagged Array, Math, Dynamic Programming and Game Theory on LeetCode.