题目大意：
石子游戏 IV
Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。
一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。
如果石子堆里没有石子了，则无法操作的玩家输掉游戏。
给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True ，否则返回 False 。
示例 1：
输入：n = 1 输出：true 解释：Alice 拿走 1 个石子并赢得胜利，因为 Bob 无法进行任何操作。
示例 2：
输入：n = 2 输出：false 解释：Alice 只能拿走 1 个石子，然后 Bob 拿走最后一个石子并赢得胜利（2 -> 1 -> 0）。
示例 3：
输入：n = 4 输出：true 解释：n 已经是一个平方数，Alice 可以一次全拿掉 4 个石子并赢得胜利（4 -> 0）。
示例 4：
输入：n = 7 输出：false 解释：当 Bob 采取最优策略时，Alice 无法赢得比赛。 如果 Alice 一开始拿走 4 个石子， Bob 会拿走 1 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 3 -> 2 -> 1 -> 0）。 如果 Alice 一开始拿走 1 个石子， Bob 会拿走 4 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 6 -> 2 -> 1 -> 0）。
示例 5：
输入：n = 17 输出：false 解释：如果 Bob 采取最优策略，Alice 无法赢得胜利。
提示：
1 <= n <= 10^5
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1510
解题思路分析：
这道题难度并不大，本题是典型的动态规划DP题目（递归加记忆数组方式）。
这种游戏类的题目切记不要真的建立2个角色去模拟比赛过程。而是要站在一个全局的角度，使用一个方法来模拟任意一个人的操作。当前函数的返回值即是当前用户（不论张三还是李四）的结果，函数中做递归调用时，子递归的返回值即是对方结果。
解题时，首先举出所有选择的可能，即小于等于n的所有非零平方数，并将这些数字存入List集合。
接下来的步骤就是基本的递归操作。首先建立递归函数，参数为当前剩余的石子堆数n。函数返回值为当前用户在还剩下n堆石头时是否可以赢得比赛。递归函数中，如果n等于0，代表已没有石子，当前用户输掉比赛，返回false。当n为非0时，我们无法立刻得知拿走几堆石头最好，因此我们需要循环每一种可能来找到最优解，循环List中所有方案，分别尝试拿1堆，4堆，9堆。。。。。如果当前堆数正好等于n，代表当前用户可以直接赢得比赛，返回true。如果当前堆数大于n，由于List中的元素是升序排列，之后的元素也都大于n，因此当前用户已没有选择，在当前情况下一定会输掉比赛，返回false。剩下的为普通情况，即我们还无法一眼看出结果，此时，拿掉当前堆数，剩下n-当前堆数的石子，并将其递归至子问题（递归至对手），如果返回结果是true，代表做出当前选择会使得对方有获胜的机会，我们还需要循环到下一个方案继续尝试。如果返回false，代表当前选择让对方无法获胜，此时直接返回true即可。
另外关于记忆数组，由于本题的递归函数中只有一个变量n，因此我们建立一个一维数组来保存已经计算过的递归结果即可。
实现代码：
Boolean[] memo; // 记忆数组
public boolean winnerSquareGame(int n) {
memo=new Boolean[n+1]; // 初始化记忆数组
// 保存所有小于等于n的非零数平方
List<Integer> list = new ArrayList<>();
int index=1;
while(index*index<=n){
list.add(index*index);
index++;
}
// 递归求解，
// 因为求的是先手用户的结果，因此递归函数的返回值即是结果
// 如果求后手选手的结果的话，将递归函数返回值取非即可。
return canWin(n,list);
}
// n：当前剩下的石子堆数
// list：所有选择
// 返回值：还剩n堆石头时，当前用户是否可以赢得比赛
boolean canWin(int n, List<Integer> list){
if(n==0) return false; // 已没有石头，输
if(memo[n]!=null) return memo[n]; // 记忆数组中存在当前解，直接返回
boolean canWin=false; // 当前用户是否可赢得比赛
for(int i=0;i<list.size();i++){ // 循环每一种选择
int count=list.get(i); // 当前选择，即选择的石头堆数
if(count==n){ // 如果堆数等于n，代表可正好拿完所有石头
canWin=true; // 当前用户获胜
break;
}
if(count>n){ // 如果堆数大于n，那么我们无法拿取石头，当前用户输
canWin=false; // 当前用户输
break;
}
// 拿了当前堆数的石头，递归至对手
// 如果对手无法获胜
if(!canWin(n-count,list)){
canWin=true; // 则当前用户获胜
break;
}
}
memo[n]=canWin; // 将结果记录到记忆数组
return canWin; // 返回当前用户是否获胜
}本题解法执行时间为89ms。
Runtime: 89 ms, faster than 100.00% of Java online submissions for Stone Game IV.
Memory Usage: 47.1 MB, less than 100.00% of Java online submissions for Stone Game IV.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1510-stone-game-iv-解题思路分析/