LeetCode 279. 完全平方数

◎

本节目标

把完全平方数视为可重复使用的物品，用一维动态规划求最少数量。

查看 LeetCode 原题

题意与边界

把正整数 n 表示成若干完全平方数之和，返回使用项数的最小值。同一个平方数可以重复使用，n 本身为平方数时答案为 1。

完全背包状态

令 dp[current] 表示组成 current 的最少平方数数量。dp[0] = 0，其余状态先设为不可达上界。枚举每个不超过 n 的平方数 square，再让 current 从小到大更新：dp[current] = min(dp[current], dp[current - square] + 1)。正序遍历允许同一平方数重复使用。

正确性依据

任何最优表示的最后一项都是某个 square，删除它后得到 current - square 的最优子问题；反过来，在该子问题最优解后加入 square 构成合法候选。枚举全部平方数并取最小值覆盖所有可能的最后一项，因此 dp[n] 最优。

代码实现

C++

C++17

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, n + 1);
        dp[0] = 0;
        for (int root = 1; root * root <= n; root++) {
            int square = root * root;
            for (int current = square; current <= n; current++) {
                dp[current] = min(dp[current], dp[current - square] + 1);
            }
        }
        return dp[n];
    }
};

Python

Python 3

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [n + 1] * (n + 1)
        dp[0] = 0
        root = 1
        while root * root <= n:
            square = root * root
            for current in range(square, n + 1):
                dp[current] = min(dp[current], dp[current - square] + 1)
            root += 1
        return dp[n]

复杂度分析

• 时间复杂度：O(n√n)。
• 空间复杂度：O(n)。

易错点

• 把 current 倒序遍历，错误地限制每个平方数只能使用一次。
• 没有设置 dp[0] = 0，导致所有状态都无法转移。
• 只测试非平方数，漏掉答案应直接为 1 的边界。

模式迁移

当候选元素可以无限重复、目标是最少数量时，可把问题视为完全背包的最小值版本。零钱兑换与本题只在“物品集合”的生成方式上不同。