【LeetCode】464.Can I Win(Medium)解题报告

【LeetCode】464.Can I Win(Medium)解题报告

tags: DP Minimax

题目地址：https://leetcode.com/problems/can-i-win/description/
题目描述：

  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.

  What if we change the game so that players cannot re-use integers?

  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.

  Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

  You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example:

Input:
maxChoosableInteger = 10
desiredTotal = 11

Output:
false

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.

  分析：这段时间一直在跟每日一题，今天这道题开始想的简单了，以为和以前那个100内说数的题一个套路，结果当然是没有a出来了hhh。然后看下小傅的视频讲解，他是用的solution1中的解法，现在还理解的不是特别的好，挖个坑，有时间再回来多想想吧。然后看leetcode讨论区里有些是用的自上而下的DP，还有用的dfs，如solution2的截图所示，侵删。

Solution1:

/*
backtracking + memorization
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
2 3
3 2
time complexity:O(2^n)
no memo: 2^n * 2^(n-1) * ··· * 2^1 = 2^((1+n)*n/2) = O(2^(n^2))

int[] state = new int[maxNumber];
recursion + hashmap<String , boolean>
还不完全理解
*/

class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if((1+maxChoosableInteger)*maxChoosableInteger/2<desiredTotal){
            return false;
        } 
        int[] state = new int[maxChoosableInteger+1];
        return canWin(state , desiredTotal , new HashMap<String , Boolean>());
    }
    public boolean canWin(int[] state, int total , Map<String , Boolean> hmap){
        String key = Arrays.toString(state);
        if(hmap.containsKey(key)){
            return hmap.get(key);
        }
        for(int i=1 ; i<state.length ; i++){
            if(state[i]==0){
                state[i] = 1;
                if(total - i<=0 || !canWin(state , total-i,hmap)){
                    hmap.put(key,true);
                    state[i]=0;
                    return true;
                }
                state[i]=0;
            }
        }
        hmap.put(key,false);
        return false;
    }
}

solution2：

Date：2017年11月8日