464. Can I Win

Description

Here

Tries

第一次尝试，很容易写出下面的solution

public final class SolutionII implements Solution {

  private final Map<Integer, Boolean> cache = new HashMap<>();
  private final boolean[] usedInteger = new boolean[21];

  public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
    int maxSum = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
    // TODO: Missed case 1: 如果<code>desiredTotal <= 0</code>那么player 1啥也不用做，就能赢
    if (desiredTotal <= 0) {
      return true;
    }

    // TODO: Missed case 2: 如果超过了<tt>maxSum</tt>, 怎么玩都取不到0，所以是lose
    if (desiredTotal > maxSum) {
      return false;
    }
    final boolean res = canIWinHelper(maxChoosableInteger, desiredTotal);
    display(usedInteger);
    return res;
  }

  private boolean canIWinHelper(int maxChoosableInteger, int desiredTotal) {
    if (desiredTotal <= 0) {
      return false;
    }
    // TODO: Missed Case 3: 这里会出现这样的情况，比如剩下desiredTotal = 13， 可以是用了 `4+9=13`, 也可以是用了`5+8=13`
    if (cache.containsKey(desiredTotal)) {
      return cache.get(desiredTotal);
    }

    boolean canIWin = false;
    for (int i = 1; i <= maxChoosableInteger; i++) {
      if (usedInteger[i]) continue;
      usedInteger[i] = true;
      if (!canIWinHelper(maxChoosableInteger, desiredTotal - i)) {
        System.out.println("Return true = " + i);
        canIWin = true;
        // TODO: Missed Case 4: 这里应该是返回之前应该要unset usedInteger[i]
        break;
      }
      usedInteger[i] = false;
    }
    cache.put(desiredTotal, canIWin);
    return canIWin;
  }

}

总共有4个Miss case:

1. Missed case 1: 如果 desiredTotal <= 0 那么player 1啥也不用做，就能赢
2. 如果超过了maxSum, 怎么玩都取不到0，所以是lose
3. 这里会出现这样的情况，比如剩下desiredTotal = 13， 可以是用了 4+9=13, 也可以是用了5+8=13,所以用getState()
4. 这里应该是返回之前应该要unset usedInteger[i]

Correct Solution

  priclass Solution {

  private final Map<Integer, Boolean> cache = new HashMap<>();
  private final boolean[] usedInteger = new boolean[21];

  public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
    int maxSum = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
    if (desiredTotal <= 0) {
      return true;
    }
    if (desiredTotal > maxSum) {
      return false;
    }
    return canIWinHelper(maxChoosableInteger, desiredTotal);
  }

  private boolean canIWinHelper(int maxChoosableInteger, int desiredTotal) {
    if (desiredTotal <= 0) {
      return false;
    }
    // Remind: the reason we don't use desiredTotal is that, it doesn't represent the visited the right status
    final int desiredState = getState();
    if (cache.containsKey(desiredState)) {
      return cache.get(desiredState);
    }

    boolean canIWin = false;
    for (int i = 1; i <= maxChoosableInteger; i++) {
      if (usedInteger[i]) continue;
      usedInteger[i] = true;
      if (!canIWinHelper(maxChoosableInteger, desiredTotal - i)) {
        canIWin = true;
        usedInteger[i] = false;
        break;
      }
      usedInteger[i] = false;
    }
    cache.put(desiredState, canIWin);
    return canIWin;
  }

  private int getState() {
    int res = 0;
    for (int i = 1; i < usedInteger.length; i++) {
      res <<= 1;
      res |= usedInteger[i] ? 1 : 0;
    }
    return res;
  }
}