279. Perfect Squares

Medium

Description

給定正整數 n，找出最少需要多少個完全平方數（1, 4, 9, 16, …）的和等於 n。

Example:

Input: n = 12 Output: 3

Intuition#

完全背包變體：物品是所有完全平方數，求湊成 n 的最少物品數。

dp[i] = 組成 i 所需的最少完全平方數個數
對每個 i，嘗試所有 j*j <= i 的完全平方數
狀態轉移：dp[i] = min(dp[i - j*j] + 1) for all valid j

Approaches#

1: Top-Down Memoization#

概念: 遞迴嘗試減去每個完全平方數，記憶化結果
時間複雜度: O(n * sqrt(n))
空間複雜度: 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#

概念: 從 1 到 n 逐步計算每個值的最少完全平方數個數
時間複雜度: O(n * sqrt(n))
空間複雜度: 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，求最少物品數
關鍵技巧: 初始化 dp[i] = i（全用 1 來湊），保證有一個合法上界；根據 Lagrange 四平方和定理，答案最多為 4