Last updated
Was this helpful?
Last updated
Was this helpful?
Time: O(1) && Space: O(1)
Let dp[i]
denote the maximum score one can get if he/she takes stones first at the position i. We only need to compare dp[0]*2 with the total sum of stone values to determine the game result.
Algorithm Step1. Calculate the suffix sum of stone values. Step2. For i = n-1, n-2, …, 0, calculate dp[i]. We need to enumerate three possible scenarios which correspond to taking 1, 2, 3 stones at this round. state transition: dp[i] = max(dp[i], suffixSum[i]-suffixSum[k+1] + suffixSum[k+1] - dp[k+1]) = max(dp[i], suffixSum[i] - dp[k+1]),for k = i, i+1, i+2, where (suffixSum[k+1] - dp[k+1]) means the score one can get when he/she takes stones secondly at the position k+1.
Step3. Compare suffixSum[0] with dp[0]*2. (Alice score: dp[0], Bob score: suffixSum[0]-dp[0])
Complexity Time: O(n) Space: O(n) In fact, we could reduce the space complexity to O(1) since we only need suffixSum[i:i+3] and dp[i:i+3]
in each iteration of Step2. To make the code clear to understand, the space optimization is not implemented in the code below.