CanIWin.java

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);
    }
}