# 1510. Stone Game IV
###### tags: `Leetcode` `Hard` `Backtracking` `Min-Max Strategy`
Link: https://leetcode.com/problems/stone-game-iv/
## 思路
dp[n]表示当我方手上有n个stones的时候会不会胜利
遍历所有小于n的平方数 如果有一个可以让对方输 那么我方就会胜利
如果都会让对方赢 我方就不会胜利
## Code

class Solution {
    public boolean winnerSquareGame(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp, -1);
        List<Integer> squares = new ArrayList<>();
        for(int i=1; i*i<=n; i++){
            squares.add(i*i);
        }
        return solve(dp, squares, n)==1;
    }
    private int solve(int[] dp, List<Integer> squares, int n){
        //1 alice win 
        //0 bob win
        if(n==1) return 1;
        if(dp[n]!=-1) return dp[n];
        for(int num:squares){
            if(num>n) break;
            if(num==n) return dp[n]=1;
            if(solve(dp, squares, n-num)==0) return dp[n]=1;
        }
        return dp[n]=0;
    } 
}