原题链接

状态定义

dp[i]: 和为 i 的完全平方数的最少数量

状态转移方程

dp[i] = Math.min(dp[i], i - j * j + 1)

dp[i] 可以由dp[i - j * j] + 1 推出，取二者中较小者。

初始化

dp[0] = 0

constnumSquares=function(n){constdp=newArray(n+1).fill(0)for(leti=1;i<=n;i++){dp[i]=ifor(letj=1;i-j*j>=0;j++){dp[i]=Math.min(dp[i],dp[i-j*j]+1)}}returndp[n]}

• 时间复杂度：O(n * sqrt(n))，sqrt 为平方根
• 空间复杂度：O(n)