// @Title: 完全平方数 (Perfect Squares)
// @Author: qisiii
// @Date: 2024-11-01 00:09:13
// @Runtime: 27 ms
// @Memory: 41.6 MB
// @comment: 完全背包-滚动数组
// @flag: GREEN
class Solution {
    //和零钱兑换一模一样，这里尝试使用滚动数组
    public int numSquares(int n) {
        int[] dp=new int[n+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;
        for(int i=1;i<=n;i++){
            for(int j=i*i;j<=n;j++){
                if(dp[j-i*i]!=Integer.MAX_VALUE){
                    dp[j]=Math.min(dp[j],dp[j-i*i]+1);
                }
            }
        }
        return dp[n];
    }
}