网站培训制度,网站建设与维护工作内容,移动端关键词优化,公司简介模板简洁大方思路#xff1a;数学
这有一点博弈论的味道#xff0c;但是我们依然可以用数学的角度去思考。
我们的入手点在这里#xff1a;
我们是先手的前提下#xff0c;一共有4个石头#xff0c;但是每个人只能一次拿其中的1-3个。在一共有4个石头的情况下#xff0c;我们无论拿…思路数学
这有一点博弈论的味道但是我们依然可以用数学的角度去思考。
我们的入手点在这里
我们是先手的前提下一共有4个石头但是每个人只能一次拿其中的1-3个。在一共有4个石头的情况下我们无论拿走几个总会剩下对手可以拿到的范围的石头个数我们必输那么反其道而行之我们不让它的总数是4个就行了。
以此类推当是8个12个等等4的倍数的时候我们可以按照4个4个的阶段进行解读因为我们总是选择最优的解法我们想赢就必须把剩余的石子个数控制在4的倍数之外。
所以我们只需要把三种可能的结果剩余石头算出来然后判断它们其中有没有不是4的倍数的石子个数有一个就证明我们可以采取其中的几个策略来实施。
class Solution {public boolean canWinNim(int n) {if(n3)return true;else{int []arrnew int[3];arr[0]n-1;arr[1]n-2;arr[2]n-3;if(arr[0]%40||arr[1]%40||arr[2]%40)return true;elsereturn false;}}
}
