Leetcode 486. Predict the Winner

Brute-force

This question is the variation of Stone Game. Let’s start with the brute-force approach. Assume n = piles.length. If we enumerate all possible paths that a player choose either the start or the end stones in the array, players switch between different layers. Each path has a length of n. For each path, we can track the sum scores of two players. At the botom of the decision tree, we compare two player's scores:

1. If player1's score is less than player2's score at all leave node, there is no chance player1 can score more than or equal to player2, so return false;
2. If player1's score is more than or equal to player2's score at all leave node, there is no chance player1 can score less than player2, so return true;
3. If the result of comparison is mixed, player1 can score more than or equal to player2. Because player1 starts first, which means he has the right to decide which path to follow. So return true.

The time complexity is $O(2^n)$. Given the constraints 1 <= n <= 20, this brute-force approach is computationally feasible. However, we can do better than that.

DP

To decrease the exponential complexity, we can consider to use dynamic programming. The hardest part for this question is to properly define memo. If you are not familiar with DP, please look at my website, there is a detailed explanation.

We can define memo[i][j] as the maximum stones a player can score in the game playing on piles[i..j], and the player plays first. The base case would be i == j, and the result would simply be piles[i]. The player can either choose piles[i] or piles[j]. Either way the other player will play optimally and the result will be memo[i + 1][j] or memo[i][j - 1]. To score maximumly, this player must let the other player score as few as possible, and his result is the sum of current piles[i...j] minus the scores of the other player. Therefore, the state transition equation is: dp[i][j] = Math.max(sum - dp[i + 1][j], sum - dp[i][j - 1]).

Complexity

• Time complexity: $O(n^2)$, $n^2$ states, each $O(1)$.
• Space complexity: $O(n^2)$, memo: $O(n^2)$ + $n^2$ function stacks, each $O(1)$

Code

class Solution {
    public boolean predictTheWinner(int[] piles) {
        // memo[i][j]: the max stones a player can score in the game playing on piles[i..j], the player plays first
        Integer[][] memo = new Integer[piles.length][piles.length];
        int sum = sum(piles);
        int score1 = dp(piles, 0, piles.length - 1, memo, sum);

        return score1 >= sum - score1;
    }

    private int dp(int[] piles, int i, int j, Integer[][] memo, int sum) {
        if (i == j)
            return piles[i];

        if (memo[i][j] != null)
            return memo[i][j];

        int score = Integer.MIN_VALUE;

        // alice choose i
        score = Math.max(score, sum - dp(piles, i + 1, j, memo, sum - piles[i]));
        // alice choose j
        score = Math.max(score, sum - dp(piles, i, j - 1, memo, sum - piles[j]));

        memo[i][j] = score;

        return memo[i][j];
    }

    private int sum(int[] piles) {
        int sum = 0;
        for (int n : piles) sum += n;
        return sum;
    }
}

PLEASE UPVOTE IF THIS WAS HELPFUL TO YOU