forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCoins in a Line III.java
More file actions
217 lines (176 loc) · 6.91 KB
/
Copy pathCoins in a Line III.java
File metadata and controls
217 lines (176 loc) · 6.91 KB
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
H
1521702603
tags: Array, DP, Game Theory, Interval DP, Memoization
还是2个人拿n个coin, coin可以有不同的value. 只不过这次选手可以从任意的一头拿, 而不限制从一头拿. 算先手会不会赢?
#### Memoization + Search
- 跟Coins in a Line II 一样, MiniMax的思想: 找到我的掠视中的最大值
- dp[i][j] 代表在[i,j]区间上的先手最多能取的value 总和
- 同样, sum[i][j]表示[i] 到 [j]间的value总和
- dp[i][j] = sum[i][j] - Math.min(dp[i][j - 1], dp[i + 1][j]);
- 这里需要search, 画出tree可以看明白是如何根据取前后而分段的.
#### 博弈 + 区间DP
(这个方法需要复习, 跟数学表达式的推断相关联)
- S(x) = X - Y, 找最大数字差. 如果最大值都大于0, 就是赢了; 如果小于0, 就输了.
- dp[i][j]表示 从index(i) 到 index(j), 先手可以拿到的最大值与对手的数字差. 也就是S(x) = X - Y.
- dp[i][j] = max{a[i] - dp[i + 1][j], a[j] - dp[i][j - 1]}
- 最后判断 dp[0][n] >= 0
#### 注意
- 如果考虑计算先手[i, j]之间的最大值, 然后可能还需要两个数组, 最后用于比较先手和opponent的得分大小 => 那么就要多开维.
- 我们这里考虑的数字差, 刚好让人不需要计算先手的得分总值, 非常巧妙.
#### 区间型动态规划
- 找出[i, j]区间内的性质: dp[i][j]下标表示区间范围 [i, j]
- 子问题: 砍头, 砍尾, 砍头砍尾
- loop应该基于区间的length
- template: 考虑len = 1, len = 2; 设定i的时候一定是 i <= n - len; 设定j的时候, j = len + i - 1;
```
/*
There are n coins in a line. Two players take turns to take a coin from one of the ends of the line
until there are no more coins left. The player with the larger amount of money wins.
Could you please decide the first player will win or lose?
Example
Given array A = [3,2,2], return true.
Given array A = [1,2,4], return true.
Given array A = [1,20,4], return false.
Challenge
Follow Up Question:
If n is even. Is there any hacky algorithm that can decide whether first player will win
or lose in O(1) memory and O(n) time?
Tags
Array Dynamic Programming Game Theory
*/
/*
Thoughts:
MiniMax concept, memoization dp.
dp[i][j]: max sum of values a player can get in range [i, j]
sum[i][j]: sum of value in range [i, j]
dp[i][j] = sum[i][j] - Math.min(dp[i + 1][j], dp[i][j - 1]);
*/
public class Solution {
public boolean firstWillWin(int[] values) {
if (values == null || values.length == 0) {
return false;
}
int n = values.length;
int[][] sum = new int[n + 1][n + 1];
int[][] dp = new int[n + 1][n + 1];
boolean[][] visited = new boolean[n + 1][n + 1];
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (i == j) {
sum[i][j] = values[i];
} else {
sum[i][j] = sum[i][j - 1] + values[j];
}
}
}
// total
int total = 0;
for (int value : values) {
total += value;
}
search(0, n - 1, visited, dp, sum, values);
return dp[0][n - 1] > total / 2;
}
private void search(int i, int j, boolean[][] visited, int[][] dp, int[][] sum, int[] values) {
if (visited[i][j]) {
return;
}
visited[i][j] = true;
if (i == j) {
dp[i][j] = values[i];
} else if (i > j) {
dp[i][j] = 0;
} else if (i + 1 == j) {
dp[i][j] = Math.max(values[i], values[j]);
} else {
search(i + 1, j, visited, dp, sum, values);
search(i, j - 1, visited, dp, sum, values);
dp[i][j] = sum[i][j] - Math.min(dp[i + 1][j], dp[i][j - 1]);
}
}
}
//using flat to mark visited; actually dp[i][j] > 0 will mean visited, since coin value > 0
public class Solution {
public boolean firstWillWin(int[] values) {
if (values == null || values.length == 0) {
return false;
}
int n = values.length;
int[][] sum = new int[n + 1][n + 1];
int[][] dp = new int[n + 1][n + 1];
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (i == j) {
sum[i][j] = values[i];
} else {
sum[i][j] = sum[i][j - 1] + values[j];
}
}
}
// total
int total = 0;
for (int value : values) {
total += value;
}
search(0, n - 1, dp, sum, values);
return dp[0][n - 1] > total / 2;
}
private void search(int i, int j, int[][] dp, int[][] sum, int[] values) {
if (dp[i][j] > 0) {
return;
}
if (i == j) {
dp[i][j] = values[i];
} else if (i > j) {
dp[i][j] = 0;
} else if (i + 1 == j) {
dp[i][j] = Math.max(values[i], values[j]);
} else {
search(i + 1, j, dp, sum, values);
search(i, j - 1, dp, sum, values);
dp[i][j] = sum[i][j] - Math.min(dp[i + 1][j], dp[i][j - 1]);
}
}
}
/*
博弈. 这题, 是区间型.
区间型标志: 每人每次只能取第一个数,或者最后一个数
翻译: 每次砍头, 或者砍尾
trick, 记录自己的数字与对手的数字和之差:
S(x) = X - Y, 找最大数字差. 如果最大值都大于0, 就是赢了; 如果小于0, 就输了.
这里我们用S(x)表示对于x先手而言的数字差, S(y)表示对于opponent y 先手而言的数字差.
假设x先手的时候, S(x) = X - Y. 这一步拿掉了大小为m的coin.
当opponent变成先手时候, 剩下的coins 被分割成x’, y’, 就有subset的S’(y) = y’ - x’
Overall S(y) = Y - X = y’ - x’ - m = S’(y) - m
同时S(x) = X - Y = -(S’(y) - m) = m - S’(y)
注意: 这里的S’(y)面对的是拿过coins剩下的局面.
dp[i][j]表示 从index(i) 到 index(j), 先手可以拿到的最大值与对手的数字差. 也就是S(x) = X - Y.
那么S(x) = X - Y = a[i] - dp[i + 1][j]; // 砍头
X = a[i]. 那里第i个coin
dp[i + 1][j]: opponent从 i 位之后能积累的最大值
a[j] - dp[i][j - 1]//砍尾
dp[i][j] = max{a[i] - dp[i + 1][j], a[j] - dp[i][j - 1]}
最后看dp[0][n] >= 0
*/
public class Solution {
public boolean firstWillWin(int[] values) {
if (values == null || values.length == 0) {
return false;
}
int n = values.length;
int[][] dp = new int[n][n];
// len = 1
for (int i = 0; i < n; i++) {
dp[i][i] = values[i];
}
// len = 2
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = len + i - 1;
dp[i][j] = Math.max(values[i] - dp[i + 1][j], values[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] >= 0;
}
}
```