給定正整數
n，找出最少需要多少個完全平方數（1, 4, 9, 16, …）的和等於n。
Example:
Input: n = 12 Output: 3
Intuition
TIP
完全背包變體：物品是所有完全平方數，求湊成 n 的最少物品數。
dp[i]= 組成i所需的最少完全平方數個數- 對每個
i，嘗試所有j*j <= i的完全平方數 - 狀態轉移：
dp[i] = min(dp[i - j*j] + 1)for all validj
Approaches
1. Top-Down Memoization — O(n * sqrt(n)) / O(n)
- Idea: 遞迴嘗試減去每個完全平方數，記憶化結果
- Time:
O(n * sqrt(n)) - Space:
O(n)
class Solution {
fun numSquares(n: Int): Int {
val memo = IntArray(n + 1) { -1 }
fun dp(rem: Int): Int {
if (rem == 0) return 0
if (memo[rem] != -1) return memo[rem]
var best = rem // 最差情況全用 1
var j = 1
while (j * j <= rem) {
best = minOf(best, dp(rem - j * j) + 1)
j++
}
memo[rem] = best
return best
}
return dp(n)
}
}⭐ 2. Bottom-Up DP — O(n * sqrt(n)) / O(n)
- Idea: 從 1 到 n 逐步計算每個值的最少完全平方數個數
- Time:
O(n * sqrt(n)) - Space:
O(n)
class Solution {
fun numSquares(n: Int): Int {
val dp = IntArray(n + 1) { it } // 最差全用 1
for (i in 1..n) {
var j = 1
while (j * j <= i) {
dp[i] = minOf(dp[i], dp[i - j * j] + 1)
j++
}
}
return dp[n]
}
}🔑 Takeaways
- Pattern: 完全背包 — 物品為完全平方數，容量為 n，求最少物品數
- Key trick: 初始化
dp[i] = i（全用 1 來湊），保證有一個合法上界；根據 Lagrange 四平方和定理，答案最多為 4