当前位置：网站首页>leetcode1025. Divisor game (simple)

leetcode1025. Divisor game (simple)

2022-04-22 14:48:00 【Heavy garbage】

Insert picture description here
Insert picture description here
Train of thought ：dp
From small to capital ：
1：alice transport
2：alice Only choose 1,bob transport ,alice win
3：alice choose 1 go to 2：alice transport ;
dp[i] Express i when alice Win or lose , hypothesis j yes i Factor of ,dp[i - j] There is an existence false, be dp[i]=true;
otherwise dp[i] Only for false

class Solution {
    
public:
    bool divisorGame(int n) {
    

        vector<int> dp(n + 1);
        if (n == 1) return false;
        if (n == 2) return true;
        dp[1] = false;
        dp[2] = true;
        for (int i = 3; i < n + 1; ++i) {
    
            int j = 1;
            for (; j < i; ++j) {
    
                if (i % j == 0 && !dp[i - j]) {
    
                    dp[i] = true;
                    break;
                }
            }
            if (j == i) dp[i] = false;
        }
        return dp[n];
    }
};

版权声明
本文为[Heavy garbage]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/04/202204221445202881.html

边栏推荐

猜你喜欢

随机推荐