石子游戏 IV 题目描述 Alice 和 Bob 正在玩一个石子游戏。游戏规则如下：有一堆石子，总数为 n。Alice 和 Bob 轮流进行自己的回合，Alice 先手。每一回合，当前玩家可以从石子堆中移除一个平方数（即 1, 4, 9, 16, ...）的石子。无法移除石子的玩家输掉游戏。假设两位玩家都以最佳状态参与游戏，请判断 Alice 是否可以赢得游戏。如果 Alice 获胜，返回 true；否则，返回 false。 解题过程 问题分析 这是一个博弈类问题，可以使用动态规划（特别是区间DP的思路）来解决。 关键点：对于给定的石子数 i，如果存在一种移除方式（移除一个平方数），使得剩下的石子数 j 是一个必败状态（即对手无论怎么走都会输），那么当前状态 i 就是必胜状态。 否则，如果所有可能的移除方式都导致对手处于必胜状态，那么当前状态 i 是必败状态。 状态定义 定义 dp[ i ] 表示当石子数为 i 时，当前玩家（先手）是否能够获胜。 dp[ i ] 为 true 表示先手获胜，false 表示先手失败。 状态转移方程 对于每个状态 i，我们尝试移除所有可能的平方数 k²（其中 k² ≤ i）。 如果存在一个 k²，使得 dp[ i - k²] 为 false（即对手处于必败状态），那么 dp[ i ] = true（当前玩家获胜）。 否则，dp[ i ] = false（当前玩家失败）。 状态转移方程：dp[ i] = ∃k (k² ≤ i 且 dp[ i - k² ] == false) 初始化 当石子数为 0 时，先手玩家无法进行任何操作，因此 dp[ 0 ] = false。 计算顺序 从 i = 1 到 n 依次计算 dp[ i ] 的值。 对于每个 i，遍历所有可能的平方数 k²（k 从 1 到 √i），检查 dp[ i - k² ] 的值。 结果提取 最终结果为 dp[ n ]，表示当初始石子数为 n 时，Alice（先手）是否能获胜。 举例说明 假设 n = 4： dp[ 0 ] = false（没有石子，先手输） i = 1：可以移除 1²=1，剩下 0（dp[ 0]=false），所以 dp[ 1 ] = true i = 2：可以移除 1²=1，剩下 1（dp[ 1]=true），没有其他选择，所以 dp[ 2 ] = false i = 3：移除 1²=1，剩下 2（dp[ 2]=false），所以 dp[ 3 ] = true i = 4：可以移除 1²=1（剩下 3，dp[ 3]=true）或 2²=4（剩下 0，dp[ 0]=false），存在一个选择使对手必败，所以 dp[ 4 ] = true 因此对于 n = 4，Alice 获胜。 这个解法的时间复杂度是 O(n√n)，空间复杂度是 O(n)。