Stone game iv

Math Dynamic Programming Game Theory

59.6% acceptance

Feb 25, 2026

1640

Alice and Bob take turns playing a game, with Alice starting first. Initially, there are n stones in a pile. On each player's turn, that player makes a move consisting of removing any non-zero square number of stones in the pile. Also, if a player cannot make a move, he/she loses the game. Given a positive integer n, return true if and only if Alice wins the game otherwise return false, assuming both players play optimally.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn winner_square_game(n: i32) -> bool {
    let n = n as usize;
    let mut dp = vec![false; n + 1];
    // dp[0] = false: no moves -> current player loses
    for i in 1..=n {
      let mut s = 1usize;
      while s * s <= i {
        if !dp[i - s * s] {
          dp[i] = true;
          break;
        }
        s += 1;
      }
    }
    dp[n]
  }
}