forked from gouthampradhan/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCanIWin.java
More file actions
78 lines (72 loc) · 2.74 KB
/
CanIWin.java
File metadata and controls
78 lines (72 loc) · 2.74 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
package dynamic_programming;
import java.util.HashMap;
import java.util.Map;
/**
* Created by gouthamvidyapradhan on 04/07/2017.
* In the "100 game," two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.
* <p>
* What if we change the game so that players cannot re-use integers?
* <p>
* For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.
* <p>
* Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.
* <p>
* You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.
* <p>
* Example
* <p>
* Input:
* maxChoosableInteger = 10
* desiredTotal = 11
* <p>
* Output:
* false
* <p>
* Explanation:
* No matter which integer the first player choose, the first player will lose.
* The first player can choose an integer from 1 up to 10.
* If the first player choose 1, the second player can only choose integers from 2 up to 10.
* The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
* Same with other integers chosen by the first player, the second player will always win.
*/
public class CanIWin {
private Map<Boolean, Map<Integer, Boolean>> DP;
/**
* Main method
*
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
System.out.println(new CanIWin().canIWin(5, 15));
}
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
int sum = 0;
for (int i = 1; i <= maxChoosableInteger; i++)
sum += i;
if (desiredTotal == 0) return true;
else if (desiredTotal > sum) return false; //if the desiredTotal exceeds the max possible sum return false;
DP = new HashMap<>();
DP.put(true, new HashMap<>());
DP.put(false, new HashMap<>());
return dp(0, maxChoosableInteger, desiredTotal, true, 0);
}
private boolean dp(int state, int M, int D, boolean P, int sum) {
if (sum >= D) return false;
Map<Integer, Boolean> map = DP.get(P);
if (map.containsKey(state))
return map.get(state);
else {
map.put(state, false);
for (int i = 0; i < M; i++) {
if ((state & (1 << i)) == 0) {
if (!dp(state | (1 << i), M, D, !P, sum + i + 1)) {
map.put(state, true);
break;
}
}
}
}
return map.get(state);
}
}