Stone Game Iii - Leetcode Solution

Problem statement:

Alice and Bob continue to play games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones. Alice and Bob take turns, with Alice going first.

On each turn, the player may take any number of stones from any of the piles. The player must take at least one stone. However, the number of stones taken on one turn cannot be more than twice the number of stones of the previous turn.

For example, if the previous player took three stones, the current player may take no more than 6 stones.

The game continues until all the stones have been taken.

Assume Alice and Bob play optimally. Return "Alice" if Alice will win, "Bob" otherwise.

Solution:

Approach:

To solve this problem, we will use the dynamic programming approach. We will first create a dp array, which will store the maximum score that can be achieved by the player for the given piles of stones. We will then use the recursive approach to fill the dp array. For each pile of stones, we will calculate the maximum score that Alice can achieve by considering all possible moves that she can make.

Algorithm:

1. Create a dp array of size n+1, where n is the length of the piles array.
2. Initialize the dp array with 0.
3. For i in range (n-1, -1, -1): a. Calculate the score for Alice if she takes 1, 2, or 3 stones from the ith pile. b. Calculate the maximum score that Alice can achieve for the rest of the piles using the dp array. c. Update the dp array for ith index with the maximum score that Alice can achieve.
4. Check if Alice has won the game or not. If dp[0] is greater than 0, then return "Alice", else return "Bob".

Let's see the Python code for the above approach.

Python code:

class Solution: def stoneGameIII(self, piles: List[int]) -> str: n = len(piles) dp = [0]*(n+1)

    for i in range(n-1, -1, -1):
        score = 0
        for j in range(i, min(n,i+3)):
            score += piles[j]
            dp[i] = max(dp[i], score - dp[j+1])
    
    if dp[0] > 0:
        return "Alice"
    elif dp[0] < 0:
        return "Bob"
    else:
        return "Tie"

Time Complexity:

The time complexity of the above approach is O(n^2), where n is the length of the piles array. This is because we are using nested loops to fill the dp array.

Space Complexity:

The space complexity of the above approach is O(n), where n is the length of the piles array. This is because we are using a dp array of size n+1 to store the maximum score that can be achieved by the player for the given piles of stones.

1