Win the Game
LC上有一系列各种Game的题，都是Minimax算法。简而言之，player1赢 = player2输。那么状态转换大概就是player1点的最大值基于上一步player2的最小值。
292. Nim Game
一堆石头每次拿1-3个问先手能否赢。很简单，如果有4个石头那么后手永远赢。
class Solution {
public boolean canWinNim(int n) {
return n % 4 != 0;
}
}
293. Flip Game
轮流将++变成—直到不可以操作。问所有可能的结果。
public class Solution {
public List<String> generatePossibleNextMoves(String s) {
List<String> res = new ArrayList<String>();
if(s == null || s.length() == 0) return res;
for(int i = 0; i < s.length()-1; i++){
if(s.charAt(i) == '+' && s.charAt(i+1) == '+'){
if(i+2 < s.length())
res.add(s.substring(0, i) + "--" + s.substring(i + 2, s.length()));
else
res.add(s.substring(0, i) + "--");
}
}
return res;
}
}
294. Flip Game II
在293的基础上问先手能不能赢。这题可以用Backtrack + memo找到所有可能性，如果出现一个先手能赢的结果就返回True。Backtrack的方法时间复杂度约等于O(N!).
class Solution {
public boolean canWin(String s) {
if(s == null || s.length() <= 1) return false;
Map<String, Boolean> map = new HashMap<>();
check(s, map);
return map.get(s);
}
private boolean check(String s, Map<String, Boolean> map) {
if(map.containsKey(s)) return map.get(s);
char[] arr = s.toCharArray();
for(int i = 1; i < arr.length; i++) {
if(arr[i - 1] == '+' && arr[i] == '+') {
arr[i - 1] = '-';
arr[i] = '-';
if(!check(new String(arr), map)) {
map.put(s, true);
return true;
}
arr[i] = '+';
arr[i - 1] = '+';
}
}
map.put(s, false);
return false;
}
}
464. Can I Win
两个人轮流选数字，不放回，第一个达到或超过target的人赢。先判断可选数字总和能否超过target，再backtrack找到能赢的可能。用bit记录当前state，用Map记录所有经过的state。Discuss, O(2^N) after memo, O(N!) without memo.
class Solution {
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
if(desiredTotal <= maxChoosableInteger) return true;
if(maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
Map<Integer, Boolean> memo = new HashMap<>();
return check(maxChoosableInteger, desiredTotal, 0, memo);
}
private boolean check(int max_num, int desire, int state, Map<Integer, Boolean> map) {
if(desire <= 0) return false;
if(map.containsKey(state)) return map.get(state);
for(int i = 0; i < max_num; i++) {
if((state & (1 << i)) == 0) {
if(!check(max_num, desire - i - 1, state | (1 << i), map)) {
map.put(state, true);
return true;
}
}
}
map.put(state, false);
return false;
}
}
375. Guess Number Higher or Lower II
猜数，猜错了就付这个数并得到范围，猜对了就得到这个数。问最少付出多少能保证猜对。利用DP的想法，memo[s][e]代表s～e范围内猜对需要付出的最少的钱，那么状态转换公式就是：
memo[s][e] = Math.min(memo[s][e], i + Math.max(memo[s][i - 1], memo[i + 1][e])) for i in [s, e]
最大值代表猜这个范围内任意一个数目的时候，都要保证能够支付坏的那个情况。最小值代表只要能够支付区间内任意一个数字就可以保证有一个猜对的解法。
O(N ^ 3), O(N ^ 2)
class Solution {
public int getMoneyAmount(int n) {
int[][] memo = new int[n+1][n+1];
return get(memo, 1, n);
}
private int get(int[][] memo, int s, int e) {
if(s >= e) return 0;
if(memo[s][e] != 0) return memo[s][e];
int min = Integer.MAX_VALUE;
for(int i = s; i <= e; i++) {
min = Math.min(min, i + Math.max(get(memo, s, i - 1), get(memo, i + 1, e)));
}
memo[s][e] = min;
return min;
}
}
486. Predict the Winner
轮流从两端拿最后数多的赢。求先手能不能赢。这种就比较典型了，dp存先后手拿到的差最大值。
O(N * N), O(N * N)
class Solution {
public boolean PredictTheWinner(int[] nums) {
int len = nums.length;
Integer[][] memo = new Integer[len][len];
return getMax(nums, memo, 0, len - 1) >= 0;
}
private int getMax(int[] nums, Integer[][]memo, int s, int e) {
if(s == e) return nums[s];
if(memo[s][e] != null) {
return memo[s][e];
}
int a = nums[s] - getMax(nums, memo, s + 1, e);
int b = nums[e] - getMax(nums, memo, s, e - 1);
memo[s][e] = Math.max(a, b);
return memo[s][e];
}
}
空间可以优化，此时必须从后向前遍历。
class Solution {
public boolean PredictTheWinner(int[] nums) {
int len = nums.length;
// dp - save difference of two players
// dp[i][j] = Max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])
int[] dp = new int[len];
for(int i = 0; i < len; i++) {
dp[i] = nums[i];
}
for(int s = len - 1; s >= 0; s--) {
for(int e = s + 1; e < len; e++) {
int a = nums[s] - dp[e];
int b = nums[e] - dp[e - 1];
dp[e] = Math.max(a, b);
}
}
return dp[len - 1] >= 0;
}
}
877. Stone Game
偶数堆一共奇数个石头，两个人从任意一端轮流拿，最后谁拿的多谁赢。问先手能否保证赢。
偶数堆的时候石头的分配总是奇数index和偶数index分开，先手永远可以选择拥有多的。O(1), O(1).
class Solution {
public boolean stoneGame(int[] piles) {
return true;
}
}
当然也可以用DP来解，万一不是偶数堆个石头呢？Minimax的想法，which is 486。
dp[i][j]代表从i到j堆石头先手能够比后手多拿的石头数目。状态转换方程：
dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
注意这里最外层循环也是以length递增循环的。O(N^2), O(N^2)
class Solution {
public boolean stoneGame(int[] piles) {
// dp[i][j] = Math.max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
int n = piles.length;
int[][] dp = new int[n][n];
for(int len = 1; len < n; len++) {
for(int i = 0; i + len < n; i++) {
dp[i][i] = piles[i];
int j = i + len;
dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] > 0;
}
}
1140. Stone Game II
在877的基础上更新了拿石头的方式。
On each player’s turn, that player can take all the stones in the first Xremaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X).
memo[i][m]代表从i到最后一堆石头，先手能拿的最多石头。所以也所有就是从i到最后一堆石头中减去先手拿了x堆之后后手变成先手能拿的最多的石头。O(N ^ 3), O(N^2).
class Solution {
public int stoneGameII(int[] piles) {
// dfs, memo[i][m] = max_x(sum[i:] - memo[i+x][max(x, m)])
int n = piles.length;
int[] sum = new int[n];
for(int i = n - 1; i >= 0; i--) {
if(i == n - 1) sum[i] = piles[i];
else sum[i] = piles[i] + sum[i + 1];
}
// M <= piles.length
int[][] memo = new int[n][n];
return find(piles, sum, memo, 0, 1);
}
private int find(int[] piles, int[] sum, int[][] memo, int i, int m) {
if(i >= piles.length) return 0;
if(2 * m >= piles.length - i + 1) return sum[i];
if(memo[i][m] != 0) return memo[i][m];
for(int x = 1; x <= 2 * m; x++) {
memo[i][m] = Math.max(memo[i][m], sum[i] - find(piles, sum, memo, x + i, Math.max(x, m)));
}
return memo[i][m];
}
}