Optimal Strategy For A Game

JavaView on GFG

Time: O(n^2)

Space: O(n^2)

Intuition

DP: both players play optimally. dp[i][j] = max coins first player can collect from coins[i..j].

Algorithm

1dp[i][j]: if player takes coins[i], opponent plays optimally on [i+1,j]: dp[i+1][j] gives opponent max, player gets sum[i..j]-dp[i+1][j].
2If player takes coins[j]: similarly dp[i][j-1].
3dp[i][j] = max(coins[i] + sum[i+1][j] - dp[i+1][j], coins[j] + sum[i][j-1] - dp[i][j-1]).

Common Pitfalls

•dp[i][j] = what first player gets. Use range sum to compute what remains. Both pick optimally.

Optimal Strategy For A Game.java

Java

// Approach: Interval DP. dp[i][j] = max coins player can collect from arr[i..j] when it's their turn.
// Time: O(n^2) Space: O(n^2)

class Solution {
    public int maximumAmount(int arr[]) {
        int n = arr.length;
        long dp[][] = new long[n][n];
        for (int i = 0; i < n; i++)
            dp[i][i] = arr[i];
        
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                long left = arr[i] + Math.min((i + 2 <= j ? dp[i + 2][j] : 0),
                        (i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0));
                long right = arr[j] + Math.min((i <= j - 2 ? dp[i][j - 2] : 0),
                        (i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0));
                dp[i][j] = Math.max(left, right);
            }
        }

        return (int) dp[0][n - 1];
    }
}

Was this solution helpful?