Keshawn_lu's Blog

Leetcode 1025. 除数博弈

动态规划
字数统计: 471阅读时长: 1 min
2020/04/29 Share

题目简介

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

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

选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。

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

示例 1：

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

示例 2：

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

提示：

1 <= N <= 1000

思路：首先我们可以知道N = 1 和 N = 2 时爱丽丝的胜负情况。那么我们将后面的N(即3 <= N <= 1000)都化简为前面已知的情况并存储下来，假如当前的数为N，若在[1, N - 1]中存在一个数x，首先满足 N % x == 0(说明爱丽丝本次可以进行操作)，其次满足dp[N - x] == false(即下一次轮到鲍勃时，无法进行操作)，满足这两点就说明爱丽丝获胜了，若循环后，没有一个x满足这两点，则爱丽丝就是输了(因为 N - x 的范围在[1, N-1]内， 即取1都不能满足，说明和N = 1的情况一样是输了)

C++代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    
    bool divisorGame(int N) {

        bool dp[1001];
        dp[1] = false;
        dp[2] = true;

        for(int i = 3; i <= N; i++){

            dp[i] = false;

            for(int j = 1; j < i; j++){

                if(dp[i - j] == false && i % j == 0){
                     // i即为N, j即为x
                    dp[i] = true;
                    break;
                } 
                    
            }
        }

        return dp[N];
    }
};
CATALOG
  1. 1. 题目简介
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网