leetcode 第 1025 题：除数博弈(C++)

1025. 除数博弈 - 力扣（LeetCode）

第一反应是动态规划：

f[i]是否为true取决于在 (0, i)之间能否找到一个因数j使得f[i-j]为false,也就是能否找到一个因数使得鲍勃必败。

class Solution {
public:
    bool divisorGame(int N) {
        vector<int> f(N+2, false);
        f[1] = false;
        f[2] = true;
        for(int i = 3; i <= N; ++i){
            for(int j = 1; j < i; ++j){
                if(i % j == 0 && !f[i - j]){
                    f[i] = true;
                    break;
                }
            }
        }
        return f[N];
    }
};

但是其实仔细分析会发现偶数先手必胜，奇数则必败。