Leetcode之动态规划(DP)专题-1025. 除数博弈(Divisor Game)
2024-08-31 20:31:54
Leetcode之动态规划(DP)专题-1025. 除数博弈(Divisor Game)
爱丽丝和鲍勃一起玩游戏,他们轮流行动。爱丽丝先手开局。
最初,黑板上有一个数字 N
。在每个玩家的回合,玩家需要执行以下操作:
- 选出任一
x
,满足0 < x < N
且N % x == 0
。 - 用
N - x
替换黑板上的数字N
。
如果玩家无法执行这些操作,就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 True
,否则返回 false
。假设两个玩家都以最佳状态参与游戏。
示例 1:
输入:2
输出:true
解释:爱丽丝选择 1,鲍勃无法进行操作。
示例 2:
输入:3
输出:false
解释:爱丽丝选择 1,鲍勃也选择 1,然后爱丽丝无法进行操作。
提示:
1 <= N <= 1000
按照题意,我们利用DP(动态规划)来求解这个问题。
先说两句题外话,这个问题是一个数学问题,只要N是偶数,爱丽丝必胜。
选数,要满足这个条件:
- 选出任一
x
,满足0 < x < N
且N % x == 0
。
偶数先手必胜。
因为先手为偶数的话,先手只需要让自己每步都保持偶数,那么他可以通过让对手得到的数为奇数,比如偶数-1就是奇数了,对手拿到奇数,那么能整除的只有奇数,奇数-奇数又回到了偶数,最后先手一定会得到最小的偶数2,然后-1让对手得到1,对手无解,必胜。
回到主题,我们用DP来求解这个问题,首先new一个长度为N+1的数组,dp[i]表示i这个数是否可以赢,如果为true则N=i可以赢,为false则输。
N=1,爱丽丝就肯定会输,所以我们首先让dp[1]=false;
然后我们从i=2开始,一直遍历到i=N
按照题意,我们让j每次从1到i-1的区间里取数,且需要满足
- 选出任一
x
,满足0 < x < N
且N % x == 0
。
这个条件,如果发现dp[j]=false,那么dp[i]就一定会赢。
class Solution {
public boolean divisorGame(int N) {
boolean[] dp = new boolean[N + 1];
dp[1] = false;
for (int i = 2; i <= N; i++) {
for (int j = 1; j < i; j++) {
if(!dp[i-j] && i%j==0){
dp[i] = true;
break;
}
}
}
return dp[N];
}
}
最新文章
- 【Win 10 应用开发】文件读写的三种方案
- C# 可视化读取文件、文件夹
- NashZhou的自我介绍
- java容器(java编程思想第四版-读书笔记)
- Jenkins实现测试环境到生产环境一键部署(Windows)
- Linux 网络编程四(socket多线程升级版)
- Grasshopper 2.0 MP Color FireWire 1394b (Sony ICX274)
- linux学习笔记4:linux的任务调度,进程管理,mysql的安装和使用,ssh工具的使用,linux网络编程
- bzoj1913
- asp.net尽量不在js里写<;%%>;
- Spring 3.x企业实用开发实战(1)
- Educational Codeforces Round 15_B. Powers of Two
- 3299: [USACO2011 Open]Corn Maze玉米迷宫
- angularjs中使用轮播图指令swiper
- RTC实时时间系统学习笔记(一)---------------UART串口
- Java基础系列--09_集合2
- win 执行puppet
- java实现二叉树的建立以及实现二叉查找树的查、插、删、遍历
- one-hot编码
- spring、mybatis事务配置和控制