To solve this problem, we need to determine the maximum number of stones you can collect if you play optimally against an opponent who also plays optimally. The game involves taking stones from either end of a row, and both players take turns.

Approach

The problem can be efficiently solved using dynamic programming (DP). The key insight is to compute the maximum difference in the number of stones between the current player and the opponent for each subarray of stones.

1. DP Table Definition: Let dp[i][j] represent the maximum difference (current player's stones minus the opponent's stones) that the current player can achieve from the subarray stones[i..j].

2. Base Case: When there is only one stone (i == j), the current player takes that stone, so dp[i][i] = stones[i].

3. Transition: For a subarray stones[i..j], the current player can take either stones[i] or stones[j]:

   • If the player takes stones[i], the opponent will play optimally on stones[i+1..j], so the difference becomes stones[i] - dp[i+1][j].
   • If the player takes stones[j], the opponent will play optimally on stones[i..j-1], so the difference becomes stones[j] - dp[i][j-1].
   • The value of dp[i][j] is the maximum of these two options.

4. Result Calculation: The total number of stones is sum(stones). Let the current player's stones be F and the opponent's stones be S. We know:

   • F + S = sum(stones)
   • F - S = dp[0][n-1]
   • Solving these gives F = (sum(stones) + dp[0][n-1]) // 2.

Solution Code

def maxStones(stones):
    n = len(stones)
    dp = [[0] * n for _ in range(n)]

    # Base case: single stone
    for i in range(n):
        dp[i][i] = stones[i]

    # Fill dp for subarrays of length >=2
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            # Current player can take stones[i] or stones[j]
            take_left = stones[i] - dp[i+1][j]
            take_right = stones[j] - dp[i][j-1]
            dp[i][j] = max(take_left, take_right)

    total = sum(stones)
    return (total + dp[0][n-1]) // 2

Explanation

• DP Table Initialization: We start by initializing the diagonal elements of the DP table since each single stone subarray gives the player that stone.
• Filling DP Table: For each subarray length from 2 to n, we compute the maximum difference for all possible starting indices. This ensures we build up the solution from smaller subarrays to larger ones.
• Result: The final result is derived from the total stones and the maximum difference for the entire array, giving the optimal number of stones the first player can collect.

This approach efficiently computes the solution with a time complexity of O(n^2) and space complexity of O(n^2), which is feasible for typical input sizes. For larger inputs, space can be optimized to O(n) by using a 1D DP array, but the 2D approach is more straightforward to understand.

Example: For stones [1,2,3,4], the maximum stones the first player can collect is 6 (take 4, then 3, totaling 6). The code correctly computes this result.

This solution handles all cases, including even and odd lengths of the stone array, and ensures optimal play from both players.

作者声明:本文包含人工智能生成内容。