forked from algorithmzuo/algorithmbasic2020
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCode03_CanIWin.java
More file actions
64 lines (58 loc) · 1.56 KB
/
Copy pathCode03_CanIWin.java
File metadata and controls
64 lines (58 loc) · 1.56 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
package class43;
// leetcode 464题
public class Code03_CanIWin {
// 这个是暴力尝试，思路是正确的，超时而已
public static boolean canIWin1(int choose, int total) {
if (total == 0) {
return true;
}
if ((choose * (choose + 1) >> 1) < total) {
return false;
}
return process1(choose, 0, total);
}
public static boolean process1(int choose, int status, int rest) {
if (rest <= 0) {
return false;
}
for (int i = 1; i <= choose; i++) {
if (((1 << i) & status) == 0) {
if (!process1(choose, (status | (1 << i)), rest - i)) {
return true;
}
}
}
return false;
}
// 暴力尝试改动态规划而已
public static boolean canIWin2(int choose, int total) {
if (total == 0) {
return true;
}
if ((choose * (choose + 1) >> 1) < total) {
return false;
}
int[] dp = new int[1 << (choose + 1)];
return process2(choose, 0, total, dp);
}
// 为什么明明status和rest是两个可变参数，却只用status来代表状态(也就是dp)
// 因为选了一批数字之后，得到的和一定是一样的，所以rest是由status决定的，所以rest不需要参与记忆化搜索
public static boolean process2(int choose, int status, int rest, int[] dp) {
if (dp[status] != 0) {
return dp[status] == 1 ? true : false;
}
boolean ans = false;
if (rest > 0) {
for (int i = 1; i <= choose; i++) {
if (((1 << i) & status) == 0) {
if (!process2(choose, (status | (1 << i)), rest - i, dp)) {
ans = true;
break;
}
}
}
}
dp[status] = ans ? 1 : -1;
return ans;
}
}