Related: LeetCode 486 - Predict the Winner
https://leetcode.com/problems/stone-game/description/
You can first pick
X.
Approach 3: 1D DP
Follow up: Use only O(N) space?
Simplify to 1D DP.
https://leetcode.com/problems/stone-game/discuss/154610/C%2B%2BJavaPython-DP-or-Just-return-true
X. DFS + cache
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)]
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.
https://leetcode.com/articles/stone-game/
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.Approach 1: Just return true
Alex is first to pick pile.
Alex can always pick odd piles or always pick even piles!
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
he picks first
Every turn, Alex can always pick even indexed piles and Lee can only pick odd indexed piles.
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
If
If
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.
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].- If you pick
piles[i], your result will bepiles[i] - dp[i + 1][j] - If you pick
piles[j], your result will bepiles[j] - dp[i][j - 1]
So we get:
We start from smaller subarray and then we use that to calculate bigger subarray.
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).
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: , where is the number of piles.
- Space Complexity: , 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.
Alex can always pick odd piles or always pick even piles!
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
he picks first
Every turn, Alex can always pick even indexed piles and Lee can only pick odd indexed piles.
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
If
If
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)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)]
