-
Notifications
You must be signed in to change notification settings - Fork 23
/
Copy pathCoins in a Line II.java
executable file
·120 lines (97 loc) · 5.04 KB
/
Coins in a Line II.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
M
1521616414
tags: DP, Array, Game Theory, Memoization, MiniMax
给一串coins, 用values[]表示; 每个coin有自己的value. 先手/后手博弈,
每次只能 按照从左到右的顺序, 拿1个或者2个棋子, 最后看谁拿的总值最大.
MiniMax的思考方法很神奇, 最后写出来的表达式很简单
#### DP, Game Theory 自考过程比较长
- 跟Coins in a line I 不一样: 每个coin的value不同.
- 用到MiniMax的思想, 这里其实是MaxiMin. Reference: http://www.cnblogs.com/grandyang/p/5864323.html
- Goal: 使得player拿到的coins value 最大化.
- 设定dp[i]: 从index i 到 index n的最大值. 所以dp[0]就是我们先手在[0 ~ n]的最大取值
- 于此同时, 你的对手playerB也想最大化, 而你的选择又不得不被对手的选择所牵制.
- 用MaxiMin的思想, 我们假设一个当下的状态, 假想对手playerB会做什么反应(从对手角度, 如何让我输)
- 在劣势中(对手让我输的目标下)找到最大的coins value sum
##### 推算表达式
- Reference里面详细介绍了表达式如何推到出来, 简而言之:
- 如果我选了i, 那么对手就只能选(i+1), (i+2) 两个位置, 而我在对方掌控时的局面就是min(dp[i+2], dp[i+3])
- 如果我选了i和(i+1), 那么对手就只能选(i+2), (i+3) 两个位置, 而我在对方掌控时的局面就是min(dp[i+3], dp[i+4])
- 大家都是可选1个或者2个coins
- 目标是maximize上面两个最坏情况中的最好结果
##### 简化表达式
- 更加简化一点: 如果我是先手, dp[i]代表我的最大值.
- 取决于我拿了[i], 还是[i] + [i+1], 对手可能是dp[i + 1], 或者是dp[i+2]
- 其实dp[i] = Math.max(sum - dp[i + 1], sum - dp[i + 2]);
- 这里的sum[i] = [i ~ n] 的sum, 减去dp[i+1], 剩下就是dp[i]的值没错了
##### Initialization
- 这个做法是从最后往前推的, 注意initialize dp末尾的值.
- dp = new int[n + 1]; dp[n] = 0; // [n ~ n]啥也不选的时候, 为0.
- sum = new int[n + 1]; sum[n] = 0; // 啥也不选的时候, 自然等于0
- 然后记得initialize (n-1), (n-2)
##### 时间/空间
Time O(n)
Space O(n): dp[], sum[]
```
/*
There are n coins with different value in a line.
Two players take turns to take one or two coins from left side
until there are no more coins left.
The player who take the coins with the most value wins.
Could you please decide the first player will win or lose?
Have you met this question in a real interview?
Example
Given values array A = [1,2,2], return true.
Given A = [1,2,4], return false.
*/
/*
Thoughts 较为复杂, 写中文:
- 跟Coins in a line I 不一样: 每个coin的value不同.
- 用到MiniMax的思想, 这里其实是MaxiMin. Reference: http://www.cnblogs.com/grandyang/p/5864323.html
- Goal: 使得player拿到的coins value 最大化.
- 于此同时, 你的对手playerB也想最大化, 而你的选择又不得不被对手的选择所牵制.
- 用MaxiMin的思想, 我们假设一个当下的状态, 假想对手playerB会做什么反应(从对手角度, 如何让我输)
- 在劣势中(对手让我输的目标下)找到最大的coins value sum
- 设定dp[i]: 从index i 到 index n的最大值. 所以dp[0]就是我们先手在[0 ~ n]的最大取值
Reference里面详细介绍了表达式如何推到出来, 简而言之:
- 如果我选了i, 那么对手就只能选(i+1), (i+2) 两个位置, 而我在对方掌控时的局面就是min(dp[i+2], dp[i+3])
- 如果我选了i和(i+1), 那么对手就只能选(i+2), (i+3) 两个位置, 而我在对方掌控时的局面就是min(dp[i+3], dp[i+4])
- 大家都是可选1个或者2个coins
- 目标是maximize上面两个最坏情况中的最好结果
更加简化一点: 如果我是先手, dp[i]代表我的最大值.
取决于我拿了[i], 还是[i] + [i+1], 对手可能是dp[i + 1], 或者是dp[i+2]
其实dp[i] = Math.max(sum - dp[i + 1], sum - dp[i + 2]);
这里的sum[i] = [i ~ n] 的sum, 减去dp[i+1], 剩下就是dp[i]的值没错了
Note:
这个做法是从最后往前推的, 注意initialize dp末尾的值.
dp = new int[n + 1]
dp[n] = 0; // [n ~ n]啥也不选的时候, 为0.
sum = new int[n + 1]
sum[n] = 0; // 啥也不选的时候, 自然等于0
然后initialize (n-1), (n-2)
*/
public class Solution {
public boolean firstWillWin(int[] values) {
if (values == null || values.length == 0) {
return false;
}
if (values.length <= 2) {
return true;
}
int n = values.length;
int[] dp = new int[n + 1]; // max value for [i ~ n]
int[] sum = new int[n + 1]; // sum of [i ~ n]
// Init dp
dp[n] = 0;
dp[n - 1] = values[n - 1]; // only 1 item for max
dp[n - 2] = values[n - 1] + values[n - 2]; // only 2 items, get all for max
// Init Sum
sum[n] = 0;
sum[n - 1] = values[n - 1];
for (int i = n - 2; i >= 0; i--) {
sum[i] = sum[i + 1] + values[i];
dp[i] = Math.max(sum[i] - dp[i + 1], sum[i] - dp[i + 2]); // Maximize the value during playerA's worst scenario
}
return sum[0] - dp[0] < dp[0];
}
}
```