LeetCode 877 - Stone Game

Related: LeetCode 486 - Predict the Winner
https://leetcode.com/problems/stone-game/description/

Alex and Lee play a game with piles of stones.  There are an even 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.  The total number of stones is odd, so there are no ties.

Alex and Lee take turns, with Alex starting first.  Each turn, a player takes the entire pile of stones from either the beginning or the end of the row.  This continues until there are no more piles left, at which point the person with the most stones wins.

Assuming Alex and Lee play optimally, return True if and only if Alex wins the game.

Example 1:

Input: [5,3,4,5]
Output: true
Explanation: 
Alex starts first, and can only take the first 5 or the last 5.
Say he takes the first 5, so that the row becomes [3, 4, 5].
If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points.
If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alex, so we return true.

It's tricky when we have even number of piles of stones. You may not have this condition in an interview.

Follow-up:

What if piles.length can be odd?
What if we want to know exactly the diffenerce of score?
Then we need to solve it with DP.
X.

Alex clearly always wins the 2 pile game. With some effort, we can see that she always wins the 4 pile game.

If Alex takes the first pile initially, she can always take the third pile. If she takes the fourth pile initially, she can always take the second pile. At least one of first + third, second + fourth is larger, so she can always win.

We can extend this idea to N piles. Say the first, third, fifth, seventh, etc. piles are white, and the second, fourth, sixth, eighth, etc. piles are black. Alex can always take either all white piles or all black piles, and one of the colors must have a sum number of stones larger than the other color.

https://leetcode.com/problems/stone-game/discuss/154610/DP-or-Just-return-true

Approach 1: Just return true

Alex is first to pick pile.
piles.length is even, and this lead to an interesting fact:
Alex can always pick odd piles or always pick even piles!

For example,
If Alex wants to pick even indexed piles piles[0], piles[2], ....., piles[n-2],
he picks first piles[0], then Lee can pick either piles[1] or piles[n - 1].
Every turn, Alex can always pick even indexed piles and Lee can only pick odd indexed piles.

In the description, we know that sum(piles) is odd.
If sum(piles[even]) > sum(piles[odd]), Alex just picks all evens and wins.
If sum(piles[even]) < sum(piles[odd]), Alex just picks all odds and wins.

So, Alex always defeats Lee in this game.

https://leetcode.com/articles/stone-game/

dp[i][j] means the biggest number of stones you can get more than opponent picking piles in piles[i] ~ piles[j].
You can first pick piles[i] or piles[j].

1. If you pick piles[i], your result will be piles[i] - dp[i + 1][j]
2. If you pick piles[j], your result will be piles[j] - dp[i][j - 1]

So we get:
dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
We start from smaller subarray and then we use that to calculate bigger subarray.

Note that take evens or take odds, it's just an easy strategy to win when the number of stones is even.
It's not the best solution!
I didn't find a tricky solution when the number of stones is odd (maybe there is).

    public boolean stoneGame(int[] p) {
        int n = p.length;
        int[][] dp  = new int[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = p[i];
        for (int d = 1; d < n; d++)
            for (int i = 0; i < n - d; i++)
                dp[i][i + d] = Math.max(p[i] - dp[i + 1][i + d], p[i + d] - dp[i][i + d - 1]);
        return dp[0][n - 1] > 0;
    }

Let's change the game so that whenever Lee scores points, it deducts from Alex's score instead.

Let dp(i, j) be the largest score Alex can achieve where the piles remaining are piles[i], piles[i+1], ..., piles[j]. This is natural in games with scoring: we want to know what the value of each position of the game is.

We can formulate a recursion for dp(i, j) in terms of dp(i+1, j) and dp(i, j-1), and we can use dynamic programming to not repeat work in this recursion. (This approach can output the correct answer, because the states form a DAG (directed acyclic graph).)

Algorithm

When the piles remaining are piles[i], piles[i+1], ..., piles[j], the player who's turn it is has at most 2 moves.

The person who's turn it is can be found by comparing j-i to N modulo 2.

If the player is Alex, then she either takes piles[i] or piles[j], increasing her score by that amount. Afterwards, the total score is either piles[i] + dp(i+1, j), or piles[j] + dp(i, j-1); and we want the maximum possible score.

If the player is Lee, then he either takes piles[i] or piles[j], decreasing Alex's score by that amount. Afterwards, the total score is either -piles[i] + dp(i+1, j), or -piles[j] + dp(i, j-1); and we want the minimum possible score.

• Time Complexity: $O(N^2)$, where $N$ is the number of piles.
• Space Complexity: $O(N^2)$, the space used storing the intermediate results of each subgame. 

  public boolean stoneGame(int[] piles) {

    int N = piles.length;

    // dp[i+1][j+1] = the value of the game [piles[i], ..., piles[j]].

    int[][] dp = new int[N + 2][N + 2];

    for (int size = 1; size <= N; ++size)

      for (int i = 0; i + size <= N; ++i) {

        int j = i + size - 1;

        int parity = (j + i + N) % 2; // j - i - N; but +x = -x (mod 2)

        if (parity == 1)

          dp[i + 1][j + 1] = Math.max(piles[i] + dp[i + 2][j + 1], piles[j] + dp[i + 1][j]);

        else

          dp[i + 1][j + 1] = Math.min(-piles[i] + dp[i + 2][j + 1], -piles[j] + dp[i + 1][j]);

      }

    return dp[1][N] > 0;

  }

  public boolean stoneGame(int[] piles) {

    Map<Integer, Long> gains = new HashMap<>();

    dfs(gains, piles, 0, piles.length - 1);

    return gains.get(piles.length - 1) > 0;

  }

  private long dfs(Map<Integer, Long> gains, int[] piles, int start, int end) {

    int pos = start * piles.length + end;

    if (gains.containsKey(pos)) {

      return gains.get(pos);

    }

    if (start < 0 || end >= piles.length) {

      return 0;// ?

    }

    if (start == end) {

      gains.put(pos, (long) piles[start]);

      return piles[start];

    }

    long gain = Math.max(piles[start] - dfs(gains, piles, start + 1, end),

        piles[end] - dfs(gains, piles, start, end - 1));

    gains.put(pos, gain);

    return gain;

  }

X.
Approach 3: 1D DP
Follow up: Use only O(N) space?
Simplify to 1D DP.

    public boolean stoneGame(int[] p) {
        int[] dp = Arrays.copyOf(p, p.length);;
        for (int d = 1; d < p.length; d++)
            for (int i = 0; i < p.length - d; i++)
                dp[i] = Math.max(p[i] - dp[i + 1], p[i + d] - dp[i]);
        return dp[0] > 0;
    }

https://leetcode.com/problems/stone-game/discuss/154610/C%2B%2BJavaPython-DP-or-Just-return-true

Alex is first to pick pile.
piles.length is even, and this lead to an interesting fact:
Alex can always pick odd piles or always pick even piles!

For example,
If Alex wants to pick even indexed piles piles[0], piles[2], ....., piles[n-2],
he picks first piles[0], then Lee can pick either piles[1] or piles[n - 1].
Every turn, Alex can always pick even indexed piles and Lee can only pick odd indexed piles.

In the description, we know that sum(piles) is odd.
If sum(piles[even]) > sum(piles[odd]), Alex just picks all evens and wins.
If sum(piles[even]) < sum(piles[odd]), Alex just picks all odds and wins.

So, Alex always defeats Lee in this game.

Alex clearly always wins the 2 pile game. With some effort, we can see that she always wins the 4 pile game.

If Alex takes the first pile initially, she can always take the third pile. If she takes the fourth pile initially, she can always take the second pile. At least one of first + third, second + fourth is larger, so she can always win.

We can extend this idea to N piles. Say the first, third, fifth, seventh, etc. piles are white, and the second, fourth, sixth, eighth, etc. piles are black. Alex can always take either all white piles or all black piles, and one of the colors must have a sum number of stones larger than the other color.

Hence, Alex always wins the game.

  public boolean stoneGame(int[] piles) {

    return true;

  }

X. DFS + cache

记忆化递归的缺点：１．有可能爆栈；２．无法降维，而DP是可以降维的。

https://leetcode.com/problems/stone-game/discuss/154660/Java-This-is-minimax-%2B-dp-(fully-detailed-explanation-%2B-generalization-%2B-easy-understand-code)

The problem was made a "trick problem," because Alex always wins, but if you want to learn the general idea behind these problems here is the explanation for other cases.

class Solution {
    int [][][] memo;
    public boolean stoneGame(int[] piles) {
        memo = new int[piles.length + 1][piles.length + 1][2];
        for(int [][] arr : memo)
            for(int [] subArr : arr)
                Arrays.fill(subArr, -1);
        
        return (helper(0, piles.length - 1, piles, 1) >= 0);
    }
    
    public int helper(int l, int r, int [] piles, int ID){
        if(r < l)
            return 0;
        if(memo[l][r][ID] != -1)
            return memo[l][r][ID];
        
        int next = Math.abs(ID - 1);
        if(ID == 1)
            memo[l][r][ID] = Math.max(piles[l] + helper(l + 1, r, piles, next), piles[r] + helper(l, r - 1, piles, next));
        else
            memo[l][r][ID] = Math.min(-piles[l] + helper(l + 1, r, piles, next), -piles[r] + helper(l, r - 1, piles, next));
        
        return memo[l][r][ID];
    }
}

This is a Minimax problem. Each player plays optimally to win, but you can't greedily choose the optimal strategy so you have to try all strategies, this is DP now.

What does it mean for Alex to win? Alex will win if score(Alex) >= score(Lee), but this also means score(Alex) - score(Lee) >= 0, so here you have a common parameter which is a score variable. The score parameter really means score = score(Alex) - score(Lee).

Now, if each player is suppoed to play optimally, how do you decide this with one variable?

Well since Alex is playing optimally, he wants to maximize the score variable because remember, Alex only wins if score = score(Alex) - score(Lee) >= 0 Alex should addto the score because he wants to maximize it.
Since Lee is also playing optimally, he wants to minimize the score variable, since if the score variable becomes negative, Lee has more individual score than Alex. But since we have only one variable, Lee should damage the score (or in other words, subtract from the score).

Now, let's think of the brute force solution. You are at the current state, say this is Alex's turn. Alex can choose either left or right, but he can't greedily pick so you try both of them, this is O(2^n) for runtime.

But realize the state you are in. You can easily memoize the this, the varying parameters are l, r, ID, where ID is the player ID (1 for Alex, 0 for Lee), hence you can make a DP/Cache table and return answer if you have discovered the state.

Finally, in your main function you call this helper function and check if you were able to get a score >= 0.

https://blog.csdn.net/fuxuemingzhu/article/details/82390672
双函数
使用递归求解。这个解法是左程云的算法讲解。

思路就是，作为先选的人，要选择从前面选和从后面选两种方案中的最大值。
作为后选的人，要选择前面选和从后面选两种方案中的最小值。

alex是先选的，所以调用f函数判断他能否赢。

直接递归超时，所以我是用了记忆化搜索减少了时间，就能通过了。
    def stoneGame(self, piles):
        """
        :type piles: List[int]
        :rtype: bool
        """
        if not piles:
            return False
        self.F = [[0 for i in range(len(piles))] for j in range(len(piles))]
        self.S = [[0 for i in range(len(piles))] for j in range(len(piles))]
        _sum = sum(piles)
        alex = self.f(piles, 0, len(piles) - 1)
        return alex > _sum / 2
     
    def f(self, piles, i, j):
        """
        先选
        """
        if i == j:
            return piles[i]
        if self.F[i][j] != 0:
            return self.F[i][j]
        curr = max(piles[i] + self.s(piles, i + 1, j), piles[j] + self.s(piles, i, j - 1))
        self.F[i][j] = curr
        return curr
     
    def s(self, piles, i, j):
        """
        后选
        """
        if i == j:
            return 0
        if self.S[i][j] != 0:
            return self.S[i][j]
        curr = min(self.f(piles, i + 1, j), self.f(piles, i, j - 1))
        self.S[i][j] = curr
        return curr
用map来完成记忆化搜索，也能通过：

class Solution(object):
 
    def stoneGame(self, piles):
        """
        :type piles: List[int]
        :rtype: bool
        """
        self.f_map, self.s_map = dict(), dict()
        _sum = sum(piles)
        alex = self.f(piles, 0, len(piles)-1)
        print(alex, _sum)
        return alex > _sum / 2.0
     
    def f(self, piles, start, end):
        if start == end:
            return piles[start]
        if (start, end) not in self.f_map:
            f_val = max(piles[start] + self.s(piles, start+1, end), piles[end] + self.s(piles, start, end-1))
            self.f_map[(start, end)] = f_val
        return self.f_map[(start, end)]
 
    def s(self, piles, start, end):
        if start == end:
            return 0
        if (start, end) not in self.s_map:
            s_val = min(self.f(piles, start+1, end), self.f(piles, start, end-1))
            self.s_map[(start, end)] = s_val
        return self.s_map[(start, end)]