LeetCode进阶-1025(动态规划)

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

原题

1025. Divisor Game

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number N on the chalkboard. On each player's turn, that player makes a move consisting of:

  • Choosing any x with 0 < x < N and N % x == 0.

  • Replacing the number N on the chalkboard with N - x.

Also, if a player cannot make a move, they lose the game.

Return True if and only if Alice wins the game, assuming both players play optimally.

Example 1:

Input: 2 Output: true Explanation: Alice chooses 1, and Bob has no more moves. Example 2:

Input: 3 Output: false Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.

Note:

1 <= N <= 1000

1025. Divisor Game 翻译版

Alice和Bob轮流玩一个游戏,Alice先手。

一开始,黑板上有一个数字N.在某个玩家的回合中,该玩家进行以下操作:

  • 选择任意整数x,x满足0 < x < N 并且N % x == 0

  • 将黑板上的数字N替换成N - x

最后,如果玩家无法选择,那么判断他游戏失败。

当且仅当Alice赢得比赛时才返回True,假设两个玩家都达到最佳状态

示例 1:

输入:2 输出:true 解释:Alice选择 1,Bob勃无法进行操作。示例 2:

输入:3 输出:false 解释:Alice选择 1,Bob勃也选择 1,然后Alice无法进行操作。 

提示:

1 <= N <= 1000

  • 本题在LeetCode上在动态规划分类下

题意分析

结合LeetCode的官方分类可以猜测出本题解题思路偏向动态规划思想,动态规划的思想核心,结果之间具有互相依赖性。至少有一种思路是动态规划方向(如果了解过斐波那契数字的解法,便很容易联想到本题动态规划的具体思路。未理解过斐波那契数解法的读者请关注笔者leetcode第509题后续博文。)。另一种思路,根据题目不妨带入具体数字不难发现一个结论,偶数情况一定会赢,奇数情况一定会输。我们考虑如何证明这个结论。

方法一:动态规划

思路:

当N为1:

无数字x可带入,输

当N为2:

带入数字x=1能赢。

当N为3:

若x为1,对手回合新N为2,根据上述推导结论N为2时对手赢,而自己输,继续尝试改变x

若x为2,无法整除舍弃

当N为4:

若x为1,对手回合新N为3,根据上述推导结论N为3时对手输,而自己赢,无需继续尝试改变x;

伪代码:

  1. 1、声明一个大小为N+1boolean数组,用于存取从1N每个数组对应输赢,数组下标表示数组,值表示输赢(初始win[1]默认为输)

  2. 2、双重循环遍历:

  3. 第一层循环从数字2到数组N循环遍历,按照从小到大;

  4. 第二层循环从1到当前外层循环数组x(不包含x),按照从小到大;

  5. i.n % x ==0 能整除时,判定对手的下一回合win[n-x]输赢,若对手输则自然当前回合能赢,将结果赢存入数组win[n]

  6. ii.否则,x自增后继续尝试i


  7. 3、遍历结束从2N的输赢结果均保留在数组中,返回win[N];

  • 注意:动态规划整体上提交结果正确,但是也由于循环次数较多,在时间空间复杂度等效率方面并不高。实际项目需结合具体场景进行算法选型

动态规划实现代码:

  1. public boolean divisorGame(int N) {

  2. boolean[] win = new boolean[N + 1];

  3. for (int n = 2; n <= N; ++n) {

  4. for (int x = 1; x < n; x++) {

  5. if (n % x == 0) {

  6. if (!win[n - x]) {

  7. win[n] = true;

  8. break;

  9. }

  10. }

  11. }

  12. }

  13. return win[N];

  14. }

方法二:根据奇偶规律证明

思路:

当N为1:赢

当N为2:赢

当N为3:输

当N为4:赢

...

发现规律N为奇数赢,N为偶数输,则转化为数学问题证明题。

证明:

  1. 一、N为奇数时


  2. 1.N为质数,则x必然只能为1,则对手回合N变成 N - 1 为数字更小的偶数;

  3. 2.N不为质数,存在x,则x必然为奇数,对手回合N变成 N - x 为数字更小的偶数;

  4. 结论:N为奇数时,对手回合必然为偶数且N减小。


  5. 二、N为偶数时我方赢


  6. 证明:

  7. 1.x等于1,对手回合N变成 N - 1 为数字更小的奇数;

  8. 2.对手回合的N必然为奇数,由一可知操作后我方的N必然为减小的偶数,我方持续令x=1

  9. 3.最终回合对手N减小为1,对手输而我方赢;

  10. 结论:N为偶数时我方赢。


  11. 二、N为奇数时我方输


  12. 证明:

  13. 1.N为质数,则x必然只能为1,而对手回合则变成偶数,由一可知,对手令x=1对手赢,我方输;

  14. 2.N不为质数,存在x,则x必然为奇数,对手回合N变成 N - x 为数字更小的偶数,由一可知,对手令x=1对手赢,我方输;

  15. 结论:N为奇数时我方输。

实现代码:

  1. public boolean divisorGame(int N) {

  2. return (N & 1) == 0;

  3. }

彩蛋

仔细观察第二种方法实现的时候,并不是使用N % 2 == 0来判断奇偶,而是通过(N & 1) == 0来判断,这便是本文的彩蛋。千里之行,始于足下,共勉之~

LeetCode进阶-1025(动态规划)

扫一扫 关注我的微信订阅号

原文始发于微信公众号(Aeiric):LeetCode进阶-1025(动态规划)