思路

跟322.零钱兑换一样的思路
都是求最小个数
这道题我的想法是先把完全平方数数组给求出来了，浪费了空间
大佬是直接在循环里判断掉了

var numSquares = function(n) {
    let nums =[]
    for(let i=1;i<=n;i++){
        if(i*i<=n){
            nums[i-1] =i*i
        }else{
            break
        }
    }
    let dp= new Array(n+1).fill(Infinity)
    dp[0] =0
    for(let i=0;i<nums.length;i++){
        for(let j=nums[i];j<=n;j++){
            dp[j] =Math.min(dp[j-nums[i]]+1,dp[j])
        }
    }
    return dp[n]
};
// 循环判断
var numSquares1 = function(n) {
    let dp = new Array(n + 1).fill(Infinity)
    dp[0] = 0
    for(let i = 1; i**2 <= n; i++) {
        let val = i**2
        for(let j = val; j <= n; j++) {
            dp[j] = Math.min(dp[j], dp[j - val] + 1)
        }
    }
    return dp[n]
｝