Stone games

Inspired by lee215, here is my solution.

from functools import lru_cache
class Solution:
def stoneGameIII(self, A: List[int]) -> str:
@lru_cache(None)
def dp(i):
# beyond the scope, return 0
if i>=len(A):return 0
# if only one element left, return this value
if i==len(A)-1:return A[-1]
# three actions: pick up 1, pick up 2, pick up 3.
# alice_score_of_alice at i =
# max(action_score_of_alice - (action_score_of_bob at i+j+1) for action in 3 cases)
res = -float('inf')
for j in range(3):
if i+j<len(A):
this_res = sum(A[i:i+j+1])-dp(i+j+1)
res = max(res, this_res)
return res

if dp(0)>0:return 'Alice'
elif dp(0)<0:return 'Bob'
else:return 'Tie'

Some other games problems

from functools import lru_cache
class Solution:
def stoneGameII(self, A: List[int]) -> int:
N = len(A)
@lru_cache(None)
def dp(i, M):
if i+2*M>=N:
return sum(A[i:])
res = -float('inf')
for j in range(2*M):
this_res = sum(A[i:i+j+1])-dp(i+j+1, max(M,j+1))
res = max(this_res, res)
return res
return (dp(0,1)+sum(A))//2

CUSUM can be used to speed up the computation a little bit.

from functools import lru_cache
class Solution:
def stoneGameII(self, A: List[int]) -> int:
N = len(A)
cusum = list(itertools.accumulate([0]+A))
@lru_cache(None)
def dp(i, M):
if i+2*M>=N:
return cusum[-1]-cusum[i]
res = -float('inf')
for j in range(2*M):
this_res = cusum[i+j+1]-cusum[i]-dp(i+j+1, max(M,j+1))
res = max(this_res, res)
return res
return (dp(0,1)+sum(A))//2
const int M = 1e5+10;
int dp[M];
class Solution {
public:
unordered_set<int> s;
vector<int> perfect;
bool helper(int n)
{
if (dp[n]!=-1)
{
return dp[n]==1;
}
if (s.find(n)!=s.end())
{
dp[n]=1;
return true;
}

for(int i=1;perfect[i]<n;++i)
{
if (n-perfect[i]>0 && !helper(n-perfect[i]))
{
dp[n]=1;
return true;
}
}
dp[n]=0;
return false;

}
bool winnerSquareGame(int n) {
memset(dp, 255, sizeof(dp));
int i=0;
while(1)
{
auto kk = i*i;
if (kk<1e5+10)
{
s.insert(kk);
perfect.push_back(kk);
}
else break;
i++;
}
return helper(n);

}
};

A very concise solution from Willam Lin

class Solution {
public:
bool winnerSquareGame(int n) {
vector<int> dp(n+1);
for(int i=1; i<=n; ++i) {
for(int j=1; j*j<=i; ++j)
dp[i]|=!dp[i-j*j];
}
return dp[n];
}
};

Data Scientist/MLE/SWE @takemobi