279. 完全平方数

[Geekhyt]

原题链接

状态定义

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

状态转移方程

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

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

初始化

dp[0] = 0

const numSquares = function(n) {
    const dp = new Array(n + 1).fill(0)
    for (let i = 1; i <= n; i++) {
        dp[i] = i
        for (let j = 1; i - j * j >=0; j++) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1)            
        }
    }
    return dp[n]
}

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