【LeetCode】石子游戏 IV [H](动态规划)
2023-09-27 14:19:51 时间
一、题目
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)
相关文章
- 算法小白如何高效、快速刷 LeetCode ?
- Leetcode: Minimum Size Subarray Sum
- Leetcode: Path Sum II
- LeetCode高频题84. 柱状图中最大的矩形,单调栈求位置i左边右边距离i最近且比i位置小的位置,然后结算面积
- LeetCode高频题300. 最长递增子序列
- LeetCode高频题55加类似新题45:跳跃游戏 II:最少需要跳多少步才能抵达终点
- [LeetCode] Search a 2D Matrix
- 团灭LeetCode跳跃游戏(相关话题:贪心,BFS)
- 132、【贪心算法】leetcode ——45. 跳跃游戏 II(贪心策略)(C++版本)
- 【算法/回溯算法】leetcode刷题路线(持续更新)
- 【LeetCode】77. Combinations (2 solutions)
- [LeetCode] 1306. Jump Game III 跳跃游戏之三
- [LeetCode] 1145. Binary Tree Coloring Game 二叉树着色游戏
- [LeetCode] 1140. Stone Game II 石子游戏之二
- [LeetCode] 968. Binary Tree Cameras 二叉树相机
- [LeetCode] N-ary Tree Level Order Traversal N叉树层序遍历
- [LeetCode] 293. Flip Game 翻转游戏
- [LeetCode] 312. Burst Balloons 打气球游戏
- [LeetCode] Bulls and Cows 公母牛游戏
- [LeetCode] 289. Game of Life 生命游戏
- [LeetCode] 29. Divide Two Integers 两数相除
- [LeetCode] 55. Jump Game 跳跃游戏
- Leetcode——4. Median of Two Sorted Arrays