当前位置：网站首页>leetcode1025. 除数博弈（简单）

leetcode1025. 除数博弈（简单）

2022-04-22 14:45:00 【重you小垃】

在这里插入图片描述
在这里插入图片描述
思路一：dp
从小到大写一下：
1：alice输
2：alice只能选1，bob输，alice赢
3：alice选1转到2：alice输；
dp[i]表示i时alice赢还是输，假设j是i的因子，dp[i - j]有一个存在false，则dp[i]=true;
否则dp[i]只能为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];
    }
};

版权声明
本文为[重you小垃]所创，转载请带上原文链接，感谢
https://blog.csdn.net/zhangjiaji111/article/details/124330761

边栏推荐

猜你喜欢

随机推荐