- Notifications
You must be signed in to change notification settings - Fork2.4k
Description
Bug Report forhttps://neetcode.io/problems/stone-game-iii
Using first solution:
class Solution: def stoneGameIII(self, stoneValue: List[int]) -> str: n = len(stoneValue) dp = [[None] * 2 for _ in range(n)] def dfs(i, alice): if i >= n: return 0 if dp[i][alice] is not None: return dp[i][alice] res = float("-inf") if alice == 1 else float("inf") score = 0 for j in range(i, min(i + 3, n)): if alice == 1: score += stoneValue[j] res = max(res, score + dfs(j + 1, 0)) else: score -= stoneValue[j] res = min(res, score + dfs(j + 1, 1)) dp[i][alice] = res return res result = dfs(0, 1) if result == 0: return "Tie" return "Alice" if result > 0 else "Bob"
Test Case:stoneValue=[17,-11,-11,-11,-6,-16,15,0,-13,3,11,6,-9,-15,14,3,-6,-2,11,15,15,5,4,13,-14,12,13,-10,8,15,6,3,8,-13,-12,-4,6,9,16,-16,-10,-16,-14,16,-8,12,-2,-5,-14,9,-1,8,1,-1,-2,12,-6,10,-2,15,11,-11,14,2,-10,5,-16,16,-9,-8,1,9,4,-16,8,5,-8,-17,-7,11,5,0,14,0,-3,10,-9,-7,3,-3,3,4,13,-17,-4,12,13,6,-9,4,-16,-5,-14,-4,-11,5,-5,-9,-5,4,-12,-3,3,-2,-11,-9,-1,-8,2,3,-6,13,11,-4,1,-2,-14,-6,-17,16,-7,2,13,13,-8,15,2,-16,-12,11,-10,-12,15,-2,7,3,-17,-15,9,7,11,16,-1,-13,13,9,-1,8,6,9,-3,16,-14,7,17,7,10,16,-17,12,-1,7,7,-3,-8,-3,0,-14,5,11,-14,-10,12,-7,-16,11,-4,-12,17,-12,13,-11,-10,-8,0,2,7,7,9,3,10,1,16,6,-15,2,15,-4,0,-17,10,4,11,1,-1,0,-17,-3,-8,-5,-17,2,17,2,9,-4,-4,10,6,17,-2,6,-3,14,-4,-10,8,-16,16,8,5,-9,2,11,-1,-16,2,5,-7,-12,-9,14,-16,-6,17,2,0,-7,-11,13,-10,5,-2,14,-17,10,-15,15,17,13,-13,13,-15,-6,3,-7,8,-3,2,-4,-17,-10,-2,0,15,-11,-6,7,-9,15,6,11,1,12,15,9,-17,-14,12,-12,6,12,-3,17,-17,-16,14,2,-7,7,-3,-1,-1,7,-10,4,11,7,-6,-16,2,-12,11,15,16,6,13,-15,-13,6,-11,14,2,9,-9,8,-8,-8,-7,-4,-1,-14,-10,3,12,9,-12,-2,-12,-13,-4,-10,4,-6,1,-13,-17,16,10,5,-3,8,-5,2,16,6,2,-5,-1,17,-5,-13,-1,3,7,-7,-9,0,-6,6,8,-17,1,-14,-5,14,13,1,-12,-13,-15,-6,14,0,-15,-13,1,-9,-16,6,12,-10,4,0,-14,-3,1,-14,-12,11,11,-4,8,17,-6,-6,-12,9,-1,-12,2,-3,-7,-2,14,13,-13,14,-9,-12,13,1,13,1,-6,11,3,-4,-4,-1,-15,2,-16,17,10,-9,15,-11,2,2,2,3,0,-16,15,17,-16,6,-1,-2,-17,4,3,-12,-6,-5,-16,-4,-6,0,-4,15,5,-17,6,-1,16,9,10,-5,-10,-11,-3,-4,5,-10,6,-6,10,4,-13,16,-16,-15,-4,0,-15,-1,-6,-7,-15,17,14,2,-2,13,-13,-7,-17,7,-10,11,-11,2,10,17,-2,-6,9,-3,12,13,16,-7,-10,-11,-11,5,5,-16,1,10,-6,11,8,16,-7,15,13,-9,-8,-5,11,-10,16,4,16,4,-14,5,13,2,14,-16,15,13,4,13,-13,14,-12,14,-2,-14,-14,-7,-6,0,4,-9,10,-6,13,2,0,-2,-3,-13,8,4,3,12,-17,-3,-9,6,-8,5,-12,13,-17,7,-15,3,16,12,14,-6,15,-12,-10,17,-4,-9,-17,17,11,12,-16,16,-15,-6,0,15,-7,10,10,7,-9,-5,12,-17,-10,2,11,10,-3,-16,5,-3,5,15,8,14,-12,1,-4,14,-14,0,13,1,10,9,5,-15,17,12,0,7,12,-13,15,16,-10,-17,-17,17,3,-7,12,-3,-1,11,-5,4,5,2,3,-10,-15,13,-16,-8,6,-8,-15,-13,0,5,-15,1,16,11,7,-5,-5,-5,7,3,-12,-17,-14,-17,-6,14,-15,10,3,2,13,-13,15,16,1,15,-1,-7,5,0,-16,-11,3,6,-12,-13,1,-16,-2,7,9,-11,-14,-6,5,5,3,12,-17,6,11,17,-6,-15,9,-16,-12,-14,-7,-2,-9,1,4,-12,15,11,6,-16,-17,2,4,9,-7,17,-7,-4,-4,-13,10,7,-7,-5,-11,-16,-7,2,-14,7,15,-7,14,-11,1,1,3,3,13,-9,14,1,9,9,-10,12,10,16,7,16,-6,15,-16,13,14,4,-9,-10,-6,-17,3,6,17,-11,-8,-8,-6,-15,2,-13,-10,-9,-4,0,14,-8,14,-8,3,-10,15,-11,-1,16,-2,16,-16,5,-7,-12,-11,15,5,-8,-17,-16,8,-8,7,-2,13,14,-9,-15,13,-11,1,-12,-11,14,8,9,-6,-2,9,2,-12,13,17,-12,7,16,-7,10,-15,1,1,-3,-16,4,-16,-10,-9,5,-7,2,-14,-6,2,0,0,-10,-4,-7,6,-1,16,-8,1,17,-11,-16,10,17,14,2,6,12,-16,3,5,-7,-7,-10,-7,-14,-3,-11,7,-15,12,-2,5,-17,3,-13,16,-7,7,7,4,-12,-8,16,-3,-2,1,-6,10,3,-10,-2,1,-11,9,12,-9,-3,14,-9,14,1,14,2,-2,14,12,7,11,17,2,-12,-2,13,-17,8,-10,7,-1,-2,-3,-11,-13,-8,5,10,1,17,8,-11,2,-11,-12,-4,-8,14,5,-7,1,-8,-1,-15,9,13,2,11,4,-15,-16,-2,-12,-9,6,-2,4,2,8,-12,10,0,-16,12,-3,7,5,5,3,13,2,16,-1,-11,14,-1,-15,12,-15,-16,-9,17,-17,-3,-10,0,0,11,8,-11,6,15,-7,-1,14,-12,11,-3,3,-16,14,-6,13,-11,11,-4,2,-16,-2,-3,3,3,-8,13,-14,8,-17,-10,14,12,13,-8,7,-8,2,6,-7,-2,-16,-12,1,11,7,15,11,7,13,-1,-3,-7,-17,11,5,-7,11,-6,-12,0,1,-2,17,14,-4,17,14,16,6,1,-3,4,12,-7,7,-10,13,12,14,11,16,11,-16,-14,-6,-2,5,-5,-5,17,16,-16,10,-10,3,-17,-5,13,-11,-4,3,4,2,11,-2,10,16,11,-2,-1,-9,13,14,5,11,7,11,-1,12,2,-14,6,-5,3,-13,-16,-6,9,6,-2,-13,-3,12,3,8,-11,-16,10,-10,9,10,15,-15,8,-10,0,-16,-4,-15,10,-8,-12,6,-3,2,-14,3,13,6,5,-7,11,-16,12,16,8,12,-9,-16,-8,6,15,14,-17,-11,-3,17,16,12,-16,-5,8,9,11,6,-11,5,2,6,-5,7,4,17,5,6,-6,-17,-6,13,-8,-10,-4,-17,16,13,-3,1,-16,-11,0,8,7,2,3,-13,3,13,-12,-4,-14,-6,3,-9,-14,-3,16,6,-11,-17,2,-7,-6,-8,-16,14,-16,13,2,-1,-7,17,-4,-9,16,4,-5,-12,16,7,-4,-6,10,8,7,4,5,9,1,-10,-15,-16,8,-11,-9,-11,-12,-12,-9,-2,-16,-16,-15,-9,13,4,7,11,0,-9,-6,13,-8,9,-17,-4,9,-5,-13,-16,2,7,17,14,-5,-17,-10,-3,6,17,14,-5,5,-17,-9,4,9,-6,16,-12,11,-9,16,-15,9,-10,1,-3,13,1,9,-14,13,-2,6,1,2,-3,5,17,10,1,-14,-1,4,-8,12,-1,-7,6,2,10,6,-16,15,12,17,7,-8,0,-17,-3,10,7,7,9,-12,-10,-17,6,-2,-8,-13,14,-6,5,5,-4,7,-5,11,15,-11,16,-13,17,16,14,-5,-13,2,16,-11,5,13,17,3,-6,-14,2,-8,-6,7,-4,15,2,14,-9,13,-3,15,10,-5,14,-2,17,-3,3,-9,11,7,0,-6,14,10,4,-14,-13,-2,16,-4,12,1,16,4,1,-1,2,-13,-6,11,2,2,-3,10,17,-2,3,8,5,10,0,0,-7,-2,-8,-17,12,4,8,3,-6,10,-14,10,-8,-2,3,-12,-16,2,-7,11,8,2,0,16,-8,10,2,-17,13,-14,-9,15,-7,-6,-4,13,7,-1,-7,-5,5,-8,6,0,17,-4,-1,3,-3,-11,15,8,-8,-10,14,-2,3,13,-10,8,14,-5,-1,1,-17,11,0,-1,-11,14,-3,-12,15,8,-2,-16,17,10,5,2,14,12,14,-10,-14,-12,17,-14,-14,3,2,1,-10,-12,-6,8,13,-5,6,-2,17,9,-15,-13,10,-10,-16,-17,2,14,10,-11,-8,-1,3,-16,8,-11,-8,0,17,7,-12,4,4,-7,11,2,-16,17,5,-5,1,2,-5,2,-10,11,-3,-5,5,-7,9,-10,14,-4,-14,-15,6,1,3,-4,-12,11,3,8,-1,8,-17,-2,-6,-2,6,-4,-5,15,12,6,14,14,16,-8,10,-5,5,-4,-17,15,9,-14,5,5,-15,-4,3,-16,15,4,-8,2,10,-5,-12,1,-12,-10,9,-10,-14,-14,-7,-11,-11,-17,-5,7,-2,-17,5,8,13,16,-16,-13,10,-4,-10,15,-12,17,5,9,9,-12,14,-7,5,-13,-7,10,10,-13,-17,17,3,3,14,-15,2,12,-2,5,-13,-6,1,7,8,16,11,12,9,-12,4,12,14,0,-17,-11,-5,-4,-10,-17,4,6,-15,-5,-12,12,2,13,-15,-3,-9,-14,-16,-12,-17,14,6,-9,1,-6,3,9,6,16,-9,-14,7,-4,7,-16,-1,-1,-15,-13,4,-12,14,8,-1,-9,7,4,5,1,-11,-12,-16,13,-6,-13,-11,14,-8,2,-16,-1,11,6,11,6,14,-13,12,-6,-13,-5,-7,-4,-3,3,0,4,-3,-7,-8,16,-16,4,6,-1,7,4,2,11,-3,0,-10,14,-10,0,-2,-4,-9,14,11,13,6,-8,14,6,17,13,10,-8,8,-14,14,15,-11,-2,17,-8,-9,-17,-6,-9,5,-11,-4,15,-7,-17,6,-3,-13,-14,-3,-9,-1,-10,8,9,-5,-5,13,-7,2,13,-3,2,4,-9,-14,-4,-16,14,5,-10,-5,4,8,8,-5,17,-9,-4,6,-7,-14,5,4,4,-5,-16,-8,14,-7,-6,7,-15,-9,-9,15]
Error:
Traceback (most recent call last):
File "/box/script.py", line 40, in main
output = solution.stoneGameIII(input)
File "/box/script.py", line 25, in stoneGameIII
result = dfs(0, 1)
File "/box/script.py", line 17, in dfs
res = max(res, score + dfs(j + 1, 0))
~~~^^^^^^^^^^
File "/box/script.py", line 20, in dfs
res = min(res, score + dfs(j + 1, 1))
~~~^^^^^^^^^^
File "/box/script.py", line 17, in dfs
res = max(res, score + dfs(j + 1, 0))
~~~^^^^^^^^^^
File "/box/script.py", line 20, in dfs
res = min(res, score + dfs(j + 1, 1))
~~~^^^^^^^^^^
File "/box/script.py", line 17, in dfs
res = max(res, score + dfs(j + 1, 0))
~~~^^^^^^^^^^
File "/box/script.py", line 20, in dfs
res = min(res, score + dfs(j + 1, 1))
~~~^^^^^^^^^^
File "/box/script.py", line 17, in dfs
res = max(res, score + dfs(j + 1, 0))
~~~^^^^^^^^^^
File "/box/script.py", line 20, in dfs
res = min(res, score + dfs(j + 1, 1))
~~~^^^^^^^^^^
File "/box/script.py", line 17, in dfs
res = max(res, score + dfs(j + 1, 0))
~~~^^^^^^^^^^
File "/box/script.py", line 20, in dfs
res = min(res, score + dfs(j + 1, 1))
~~~^^^^^^^^^^
File "/box/script.py", line 17, in dfs
res = max(res, score + ...
stderr limit exceeded