除数博弈(dp)

水深无声 2022-12-07 12:21 166阅读 0赞

题意：  
爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：

选出任一 x，满足 0 < x < N 且 N % x == 0 。
    用 N - x 替换黑板上的数字 N 。

如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 False。假设两个玩家都以最佳状态参与游戏。

示例 1：

输入：2  
输出：true  
解释：爱丽丝选择 1，鲍勃无法进行操作。

示例 2：

输入：3  
输出：false  
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

思路：  
用一个数组来保存信心：第一个数字是N，这位先手玩家能否必胜（true or false）  
结束的边界：  
dp\[0\] = false;  
dp\[1\] = ture;  
状态转移：  
dp\[N\]时，需要从 1 <= x < N 选一个数能整除N的数x，若选择这个数之后，先一个玩家必输，那么先手玩家就一定能赢了。  
这里玩家必输用 ！dp\[N-x\]即可表示。

代码展示：

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

vec初始化方法  
转载于：https://www.cnblogs.com/jianfeifeng/p/11014686.html  
(1)不带参数的构造函数初始化  
// 初始化一个size为0的vector  
vector abc;  
(2)带参数的构造函数初始化  
// 初始化size，但每个元素值为默认值  
vector abc(10); // 初始化了10个默认值为0的元素  
// 初始化size，并且设置初始值  
vector cde(10, 1); // 初始化了10个值为1的元素  
(3)通过数组地址初始化  
int a\[5\] = \{1,2,3,4,5\};  
// 通过数组a的地址初始化，注意地址是从0到5（左闭右开）  
(4)通过同类型vector初始化  
vector a(5, 1);  
// 通过a初始化  
vector b(a);

gcc编译错误 warning: control reaches end of non-void function|

这个警告是说的函数末尾没有返回值，一般情况下给函数加一个返回值就行，哪怕没必要，你写一个"return 1"也不会浪费你太多时间，不是吗？