leetcode 1025: Divisor Game

本文主要是介绍leetcode 1025: Divisor Game，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode 1025: Divisor Game

题意：Alice和Bob轮流玩游戏，Alice先玩。

给一个数N，对于这个数，都做下面两个操作：

第一步：选择一个数X，0<X<N,并且N%X==0;

第二步：N=N-X。

如果不能操作，就是输了。

思路：简单博弈吧。dp[i]表示当数是i的时候，当前选择的人会不会赢。

那么，dp[1]是输。

当i%j==0,dp[i]可以有dp[i-j]中false的转移过来了。无法转移，说明这个人必输。

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

 

这篇关于leetcode 1025: Divisor Game的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---