LeetCode 1510: Stone Game IV

Explanation:

• This problem can be solved using dynamic programming.
• We will create a dp array to store the result of each number of stones from 1 to n.
• We iterate through the numbers from 1 to n and calculate if Alice can win the game by removing a square number of stones.
• If Alice can make a move such that the remaining stones would lead Bob to lose the game, then Alice wins.
• We return the result for n = 1 as true because Alice starts the game.

Time Complexity: O(n√n) Space Complexity: O(n)

class Solution {
    public boolean winnerSquareGame(int n) {
        boolean[] dp = new boolean[n + 1];
        dp[0] = false;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                if (!dp[i - j * j]) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
}