Cocolib

Appearance

On this page

完全平方数 ​

TIP

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

**完全平方数 **是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

思路 ​

js
var numSquares = function(n) {
    //构造完全平方数数组，根据题目给出的 n 的范围
    let coins = []
    for(let i=0;i<=100;i++){
        coins.push(i*i)
    }
    console.log(coins)
    //下面的解法和 “零钱兑换” 几乎相同
    const INT_MAX = 10e4+5
    let dp = Array(n + 1).fill(INT_MAX)
    let res = []
    dp[0] = 0
    for(let i=0;i<coins.length;i++){
        for(let j=coins[i];j<=n;j++){
            if( dp[j-coins[i]] != INT_MAX) 
                dp[j] = Math.min(dp[j-coins[i]]+1, dp[j])
        }
        res.push([...dp])
    }
    console.log(res)
    return dp[n]!=INT_MAX?dp[n]:-1
};