Can I Win Problem


Description

LeetCode Problem 464.

In the “100 game” two players take turns adding, to a running total, any integer from 1 to 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 from 1 to 15 without replacement until they reach a total >= 100.

Given two integers maxChoosableInteger and desiredTotal, return true if the first player to move can force a win, otherwise, return false. Assume both players play optimally.

Example 1:

1
2
3
4
5
6
7
8
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.

Example 2:

1
2
Input: maxChoosableInteger = 10, desiredTotal = 0
Output: true

Example 3:

1
2
Input: maxChoosableInteger = 10, desiredTotal = 1
Output: true

Constraints:

  • 1 <= maxChoosableInteger <= 20
  • 0 <= desiredTotal <= 300


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution { 
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if(maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
        vector<int8_t> vis(1 << maxChoosableInteger, -1);
        return isWinState(0, maxChoosableInteger, desiredTotal, vis);
    }
private:
    bool isWinState(int used, int maxChoose, int desire, vector<int8_t>& vis){
        if(~vis[used]) return vis[used];
        for(int i = maxChoose; i > 0; --i){
            if(used & (1 << (i - 1))) continue;
            if(i >= desire || !isWinState(used | (1 << (i - 1)), maxChoose, desire - i, vis))
                return vis[used] = 1;
        }
        return vis[used] = 0;
    }
};




Related Posts

Max Area Of Island Problem

LeetCode 695. You are given an m x n binary...

Employee Importance Problem

LeetCode 690. You have a data structure of employee information,...

Cracking The Safe Problem

LeetCode 753. There is a safe protected by a password....

Couples Holding Hands Problem

LeetCode 765. There are n couples sitting in 2n seats...

Contain Virus Problem

LeetCode 749. A virus is spreading rapidly, and your task...

Construct String From Binary Tree Problem

LeetCode 606. Given the root of a binary tree, construct...