0279. Perfect Squares ===================== 题目信息 -------- :题号: 0279 :难度: Medium :主题: 正整数拆分、完全平方数、最少项数 :原题: `LeetCode 0279 `_ :重点: 每一项必须是正整数的平方、同一平方数可以重复使用、返回组成目标和的最少项数 题目重述 -------- 给定正整数 ``n``,把它表示为若干个完全平方数之和,并返回所需完全平方数的最少数量。完全平方数是某个整数平方得到的数,例如 ``1``、``4``、``9`` 和 ``16``;同一个完全平方数可以在表示中重复出现。 ``n`` 位于 ``[1, 10^4]``。题目只要求最少项数,不需要返回具体拆分方案。因为 ``1`` 本身是完全平方数,任何合法输入都一定可以表示,返回值至少为 1。 自建示例 -------- 最优方案重复使用同一平方数: .. code-block:: text 输入:n = 18 输出:2 解释:18 = 9 + 9,只需要两个完全平方数;不存在单个完全平方数等于 18。 目标本身是完全平方数: .. code-block:: text 输入:n = 16 输出:1 解释:16 = 4²,本身就是完全平方数,所以最少只需一项。 按目标和建立 DP --------------- 令 ``dp[x]`` 表示组成整数 ``x`` 所需的最少平方数个数。``dp[0]=0``;对每个 ``x>=1``, 枚举不超过 ``x`` 的平方 ``square=j*j``,最后一个加数取它时有: .. math:: dp[x] = 1 + \min_{j^2\le x} dp[x-j^2] 同一个平方数可以重复使用,因为每次只从更小的目标状态转移,之后仍可再次选择相同的 ``j*j``。 初始化为 ``x`` 是使用 ``1`` 重复 ``x`` 次的可行上界。 正确性说明 ---------- 任意最优表示都有一个最后平方数 ``j*j``,去掉它后剩余部分是 ``x-j*j`` 的合法表示, 其最少项数至少为 ``dp[x-j*j]``;反过来,任取一个候选平方和该最优剩余表示都能构成 ``x`` 的表示。 枚举所有可能最后项并取最小,得到且只得到最优值。按 ``x`` 递增计算时所有依赖状态已经确定。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int numSquares(int n) { std::vector dp(n + 1, 0); for (int value = 1; value <= n; ++value) { dp[value] = value; for (int root = 1; root * root <= value; ++root) { dp[value] = std::min( dp[value], dp[value - root * root] + 1); } } return dp[n]; } }; 代码分析 -------- 对每个 ``value`` 枚举 ``O(sqrt(value))`` 个平方,时间复杂度为 ``O(n sqrt(n))``, DP 数组额外空间为 ``O(n)``。``root*root`` 在题目 ``n<=10^4`` 下不会溢出;算法不需要记录具体拆分方案。