[LeetCode] 1025. Divisor Game

摘要:
dp[i]=dp[i]||!dp[i-x];//dp[i-x]==false?

Description

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. 1 <= N <= 1000

Analyse

黑板上有个整数N,每个人都作如下两个操作

  • 选择一个整数xx 满足 0 < x < NN % x == 0
  • N 变成 N - x

无法选择出满足条件的整数x时输

Alice先手

两个人作出的选择都是最优的

动态规划

  • 定义dp[i] 为当N为i,且轮到Alice选择时是否会胜利

  • 找出递推关系

dp[i] = true    ## 存在x,满足(dp[i - x] == false) && (N % x == 0) && (1 < x < N)
        false   ## 其他

给出初值

dp[0] = false

dp[1] = true

最终代码

bool divisorGame(int N) {
    bool dp[N+1] = {false}; // 用false初始化为长度为N+1的dp数组

    for (int i = 2; i <= N; i++) {
        for (int x = 1; x < i; x++) {
            if (i % x == 0) {   // N % x == 0 ?
                dp[i] = dp[i] || !dp[i-x];  // dp[i - x] == false ?
            }
        }
    }

    return dp[N];
}

找规律

对这道题来说,只有N一个输入,且N定义的是dp的长度,dp的值对于所有的N来说都是一样的,可以先手动算几个,这里计算N=6

N123456
结果xxx

N=2时,Alice选择x=1,胜

N=3时,Alice选择x=1,败

N=4时,Alice选择x=1,Bob面对N=3的情况,Alice胜,这里Alice如果选择2的话就输了(但题目说玩家做出的选择都是最优的)

N=5时,Alice选择x=1,Bob面对N=4的情况,Bob胜,Alice败

N=6时,Alice选择x=1,Bob面对N=5的情况,Bob败,Alice胜

看出规律,只要轮到Alice的时候N是偶数,Alice就赢定了

用位运算 (N & 1) == 0 来判断奇偶

bool divisorGame(int N) {
    return (N & 1) == 0;
}

简单的证明

  • 谁拿1谁就输

  • N为奇数时,Alice必输
    奇数的因子也是奇的,无论Alice选什么,剩下的N-x为偶数,x < N,N-x至少为2,Bob再选1,N-x又变成了奇数,重复这个操作,最后Alice会拿到1

  • N为偶数时,Alice必胜
    Alice每次选1,Bob就拿到了奇数,Alice胜

References

  1. Proof of returning N % 2 == 0

免责声明:文章转载自《[LeetCode] 1025. Divisor Game》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇IBM Cognos Business Intelligence Serverv10.1.1以及Samples for Oracle安装部署【转】SpringCloud之Config配置中心+BUS消息总线原理及其配置下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

svn常见问题汇总

要添加到版本库,必须更新工作副本中的文件。5.更新时,系统会提示您文件冲突,将工作副本中的文件与服务器中的文件进行比较“当版本管理系统更改计算机上的工作副本时”,它会尝试将您的意图写入计算机上的日志文件,因此日志文件记录可能与您的上次工作状态不一致。Subversion客户端将在提交内容之前在本地工作副本中写入日志。首先删除隐藏文件夹中tmp下的临时文件。服...

TortoiseGit安装、配置(Git 小乌龟安装)

然后关闭5ToroiseGit。以克隆验证中心项目为例,验证TortoiseGit配置是否正确。注意:在克隆代码之前,请确保您具有相关的项目代码权限。如果您没有权限,请具有主权限的同事帮助您分配登录gitlab的权限,在本地目标下载目录中获取SSH链接地址,右键单击--˃TortoiseGit--˃克隆,然后将SSH链接地址粘贴到URL,单击“确定”确认项目...

Java switch 枚举

Switch可以使用int.short、char、Enum和String其中,Enum是1.5之后的新特性,String是java8的新特性。所以正确的写作应该如下。...

可用的rtmp互联网地址

Rtmp:vlc使用ffmpeg获取Rtmp网络流。代码文件路径:vlc-2.2.1 modulesassesavio。hvlc-2.2.1模块。c在模块的开放回调函数OpenAvio中,使用以下代码打开rtmp网络流。avio_打开(&amp;avio_FLAG_READ);//或者这个avio_open2(&amp;sys-&gt...

Google Drive 里的文件下载的方法

Google Drive不提供创建直接下载链接的选项,但您可以通过更改链接形式在本地保存共享内容。例如,通过Google Drive共享的文件链接是:https://drive.google.com/file/d/FILE_ID/edit?usp=sharing如果您将其更改为以下修改版本,然后通过浏览器打开,则将直接下载该文件:https://drive....

firefox插件-HackBar介绍与试用

HackBar实际上是一个包含一些黑客常用工具的小工具包。它的主要目的是帮助开发人员对代码进行安全审计优点是:-MD5/SHA1/SHA256哈希MySQL/MSSQLServer/Oracle快捷方式XSSulfunctions文本区域的URL重定向不会受到影响-MD5/SHA1/SHA 256哈什排列等-MySQL/MMSQLServer/Oacle快捷...