Stone Game V - Leetcode Solution

The Stone Game V problem on LeetCode is a dynamic programming problem that requires you to find the maximum score that two players can get while playing a game with a set of stones.

Problem Statement:

There are n stones arranged in a row. Alice and Bob are playing a game where each player takes turns removing a stone from either end of the row. The player who takes the last stone wins.

Alice goes first. Both players play optimally.

You are given an integer array stoneValue of length n where stoneValue[i] represents the value of the ith stone.

Return the maximum possible score of Alice.

Solution:

To solve this problem, we can use dynamic programming. We can start by defining a function, dp[i][j], that returns the maximum score that can be obtained by playing the game with the stones from i to j.

To compute dp[i][j], we can try removing each stone from either end of the row and see the maximum score we can get. We can do this recursively by considering the new state of the game after each move.

If Alice takes a stone from the left end of the row, the total score will be stoneValue[i] plus the maximum score that Bob can obtain from the remaining stones. Similarly, if Alice takes a stone from the right end of the row, the total score will be stoneValue[j] plus the maximum score that Bob can obtain from the remaining stones.

The maximum score that Bob can obtain can be obtained by considering all the possible moves he can make and taking the minimum of the scores that Alice can obtain for each move.

Hence, the recurrence relation that we can use to compute dp[i][j] is:

dp[i][j] = max(stoneValue[i] + min(dp[i+1][j] - stoneValue[i+1], dp[i+2][j] - stoneValue[i+2], ..., dp[j][i+1] - stoneValue[j]), stoneValue[j] + min(dp[i][j-1] - stoneValue[j-1], dp[i][j-2] - stoneValue[j-2], ..., dp[j-1][i] - stoneValue[i]))

The base case for this recurrence relation would be when i = j, in which case the score would be stoneValue[i].

Finally, we can compute dp[0][n-1], which would give us the maximum score that Alice can obtain by playing optimally.

Python Code:

Here is the code to solve the Stone Game V problem on LeetCode:

def stoneGameV(stoneValue: List[int]) -> int: n = len(stoneValue) dp = [[0]*n for _ in range(n)] for i in range(n): dp[i][i] = stoneValue[i] for l in range(2, n+1): for i in range(n-l+1): j = i + l - 1 for k in range(i, j): left_sum = sum(stoneValue[i:k+1]) right_sum = sum(stoneValue[k+1:j+1]) if left_sum < right_sum: dp[i][j] = max(dp[i][j], left_sum + dp[i][k]) elif left_sum > right_sum: dp[i][j] = max(dp[i][j], right_sum + dp[k+1][j]) else: dp[i][j] = max(dp[i][j], left_sum + max(dp[i][k], dp[k+1][j])) return dp[0][n-1]

1