完全平方数 图解题解

这道题到底在问什么

n

12

输出

3，因为 12 = 4 + 4 + 4

先想最直接的笨办法

想凑出 x，就枚举最后放下的那枚平方数 sq；放下它之前已经凑好 x−sq，所以 dp[x] = dp[x−sq] + 1，对所有可用的 sq 取最小。（动画第 4 步）

最优解：一步一步想明白

1. 3拿 n＝12 试贪心：先减最大的 9，剩 3，再减 1、1、1，一共 4 枚。但 4+4+4 只要 3 枚。贪心错了，因为最大平方数不一定在最优解里。
2. 4想凑出 x，就枚举最后放下的那枚平方数 sq；放下它之前已经凑好 x−sq，所以 dp[x] = dp[x−sq] + 1，对所有可用的 sq 取最小。
3. 5dp[0]=0（凑出 0 需要 0 枚），其余暂记 ∞凑出 0 不需要任何平方数，所以 dp[0]＝0。其余位置先填无穷，表示「还没找到办法」。
4. 6只用 1 时，dp[x] = dp[x−1] + 1 = x第一枚硬币只用 1：凑 4 就放四个 1，dp[4]＝4。全用 1 一定能凑出来，但枚数最多——这是保底解，后面更大的平方数来把它压小。
5. 7dp[4] = min(旧 4, dp[0] + 1) = 1现在轮到平方数 4。凑 4 时，回头看 dp[4−4]＝dp[0]＝0，再 +1 就是一枚 4。比原来的 4 枚 1 好太多，dp[4] 从 4 降到 1。
6. 8dp[8] = min(旧 8, dp[4] + 1) = 2这是 sq＝4 这一轮从左往右刚算到 dp[8] 的中途快照：凑 8 时回看 dp[8−4]＝dp[4]＝1，再加一枚 4，就是 4+4＝两枚。它右边的 dp[9..12] 还停在上一轮全用 1 的旧值（9、10、11、12），扫描的指针还没走到，等会儿才轮到它们被压小。
7. 9dp[12] = min(用 4 这条, 旧值)凑 12 时回看 dp[12−4]＝dp[8]＝2，再加一枚 4，就是 4+4+4＝三枚。dp[12] 从 12 直接掉到 3。这就是动态规划的核心动作：站在大问题的肩膀上回看小问题。
8. 10dp[9] 被 9 压到 1，但 dp[12] 守住 3最后一枚平方数 9 上场：dp[9] 被压到 1。再试 dp[12] 走 9 这条＝dp[3]+1＝4，没有 3 好，所以 dp[12] 守住 3。扫完所有平方数，dp[12]＝3 就是答案。
9. 13完全背包的灵魂：站在 x，枚举最后一枚平方数 sq，答案就是 dp[x−sq]+1 取最小。记住这句，零钱兑换、组合总和都是它。
10. 15贪心 9+1+1+1 = 4 枚 ＞ DP 的 3 枚贪心先抓最大的 9，剩下 3 只能补三个 1，合计 4 枚。DP 不迷信最大值，老老实实比较两条路，选出 4+4+4 这条只要 3 枚。这就是为什么这题必须用 DP。
11. 19完全平方数是「完全背包求最少个数」的原子题。把硬币换成任意面额就是零钱兑换 322，把 min 换成计数就是组合总和 IV。想吃透这一类，去专题里连刷，卡住就问小欧或开通关训练。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0] + [10**9] * n          # dp[0]=0, 其余无穷
        squares = [i*i for i in range(1, int(n**0.5)+1)]
        for sq in squares:              # 枚举每个平方数(硬币)
            for x in range(sq, n + 1):  # 正序=完全背包,可重复用
                dp[x] = min(dp[x], dp[x - sq] + 1)
        return dp[n]

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, 1e9);
        dp[0] = 0;
        for (int i = 1; i * i <= n; ++i) {   // 平方数 i*i
            int sq = i * i;
            for (int x = sq; x <= n; ++x)    // 正序遍历容量
                dp[x] = min(dp[x], dp[x - sq] + 1);
        }
        return dp[n];
    }
};

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 1_000_000_000);   // 安全大数当无穷,+1 不溢出
        dp[0] = 0;
        for (int i = 1; i * i <= n; i++) {   // 平方数 i*i
            int sq = i * i;
            for (int x = sq; x <= n; x++)    // 正序遍历容量
                dp[x] = Math.min(dp[x], dp[x - sq] + 1);
        }
        return dp[n];
    }
}

# 完全背包·求最少个数 通用骨架（把 ___ 填上即可迁移）
dp = [0] + [INF] * target        # dp[0]=0 是地基
for item in items:               # ___: 可重复用的物品(平方数/硬币面额)
    for x in range(item, target+1): # 正序=完全背包(可重复)
        dp[x] = min(dp[x], dp[x-item] + 1)  # +1=放下这一个 item
return dp[target] if dp[target] < INF else -1  # 凑不出返回 -1

// 完全背包·求最少个数 通用骨架
vector<int> dp(target + 1, INF);
dp[0] = 0;
for (int item : items)                 // 可重复用的物品
    for (int x = item; x <= target; ++x)  // 正序
        dp[x] = min(dp[x], dp[x - item] + 1);
return dp[target] < INF ? dp[target] : -1;

// 完全背包·求最少个数 通用骨架
int[] dp = new int[target + 1];
Arrays.fill(dp, INF); dp[0] = 0;
for (int item : items)                  // 可重复用的物品
    for (int x = item; x <= target; x++)   // 正序
        dp[x] = Math.min(dp[x], dp[x - item] + 1);
return dp[target] < INF ? dp[target] : -1;

复杂度

面试官可能追问