Games

Stone games

5379. Stone Game III

`from functools import lru_cacheclass 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

1140. Stone Game II

`from functools import lru_cacheclass 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_cacheclass 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`

5447. Stone Game IV

`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

More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi