网站建设接单,apache做网站,如何建立网站数据库连接,滨湖区知名做网站选哪家1510. 石子游戏 IV - 力扣#xff08;LeetCode#xff09; 一、题目
Alice 和 Bob 两个人轮流玩一个游戏#xff0c;Alice 先手。
一开始#xff0c;有 n 个石子堆在一起。每个人轮流操作#xff0c;正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。
如果石… 1510. 石子游戏 IV - 力扣LeetCode 一、题目
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
二、代码
class Solution {public static boolean winnerSquareGame(int n) {// dp[i]:总共i个石子时,先手会不会赢boolean[] dp new boolean[n 1];for (int i 1; i n; i) {for (int j 1; j * j i; j) {// 当前的先手决定拿走 i * i 这个平方数// 它的对手会不会赢 dp[i - j * j]// 如果对手输了就说明自己赢了返回true。后手输先手就赢if (!dp[i - j * j]) {dp[i] true;break;}}}return dp[n];}
}
三、解题思路
这就是一道非常简单的动态规划题目。详细见注释复杂度O(N *√N)
