464. Can I Win.

464. Can I Win.

Can I Win 제가 이길 수 있을까요?

제목 링크

제목 설명

문제 분석

방법 상태 압축 동태 기획

알고리즘 설명

참조 코드

제목 링크
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.
제목 분석
이 문제는 전형적인 상태 압축 동태 기획 문제다.주어진 문제는 NP이지만 데이터 규모가 비교적 작고 2진법으로 상태를 나타내며 동적 기획의 사상을 이용하여 곱셈의 상태를 지수의 상태로 압축할 수 있다.int 형식은 20자리가 넘는 길이가 있기 때문에 하나의 int로 상태를 표시할 수 있으며 어떤 수를 선택하면 대응하는 위치를 1으로 할 수 있다.다음은 몇 가지 상황을 분석한다. - 선택할 수 있는 수를 선택하면 desiredTotal에 도달하거나 초과할 수 있을 때 필승 상태이다. - 선택할 수 있는 수를 선택하면 필승 상태에 도달한다. (현재 유저는 어느 수를 선택하든 다음 유저는 필승 국면이다. 즉, 그가 반드시 지는 것이다) 필승 상태이다. - 선택할 수 있는 수를 선택하면필수 상태에 도달할 수 있다(현재 유저는 반드시 이 상태를 선택할 것이다. 다음 단계에 그의 상대는 필수이기 때문에 그의 승리를 보장한다). 필승 상태를 위해 (문제에서 두 유저가 한 걸음 한 걸음 가장 좋은 선택을 하기 때문에 유저는 반드시 승리할 수 있는 수를 선택할 것이다)
방법: 상태 압축 동적 계획
알고리즘 설명

은 간단한 계산을 통해 직접 답을 얻을 수 있는 경우를 제외한다.

desiredTotal <= 1: 1 직접 선택

승리

옵션 숫자 합계는 desiredTotal보다 작음

의 옵션 숫자 합계가 desiredTotal: maxChoosableInteger보다 작으면 홀수로 승리할 수 있으며, 그렇지 않으면

으로 승리할 수 없습니다.

은 상태 이동 방정식을 이용하여 검색을 하고 검색에서 상태의 승패 상황을 기록한다(1은 필승, -1은 필수),

의 중복 계산을 피한다.
참조 코드

class Solution {
private:
    int max;
    vector<int> f;

public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        max = maxChoosableInteger;
        f = vector<int>(1 << 20, 0);
        if (desiredTotal <= 1)
            return true;
        int sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
        if (sum < desiredTotal)
            return false;
        else if (sum == desiredTotal)
            return maxChoosableInteger % 2;
        else
            return dfs(desiredTotal, 0);
    }

    bool dfs(int total, int state) {
        if (total <= 0)
            return false;
        else if (f[state] > 0)
            return true;
        else if (f[state] < 0)
            return false;
        else {
            for (int i = 0; i < max; i++)
                if (!(state & 1 << i) && !dfs(total - i - 1, state | 1 << i)) {
                    f[state] = 1;
                    return true;
                }
            f[state] = -1;
            return false;
        }
    }
};