0279. Perfect Squares

题目信息

题号:

0279

难度:

Medium

主题:

正整数拆分、完全平方数、最少项数

原题:

LeetCode 0279

重点:

每一项必须是正整数的平方、同一平方数可以重复使用、返回组成目标和的最少项数

题目重述

给定正整数 n,把它表示为若干个完全平方数之和,并返回所需完全平方数的最少数量。完全平方数是某个整数平方得到的数,例如 1、4、9 和 16;同一个完全平方数可以在表示中重复出现。

n 位于 [1, 10^4]。题目只要求最少项数,不需要返回具体拆分方案。因为 1 本身是完全平方数,任何合法输入都一定可以表示,返回值至少为 1。

自建示例

最优方案重复使用同一平方数:

输入:n = 18
输出:2
解释:18 = 9 + 9,只需要两个完全平方数;不存在单个完全平方数等于 18。

目标本身是完全平方数:

输入:n = 16
输出:1
解释:16 = 4²,本身就是完全平方数,所以最少只需一项。

按目标和建立 DP

令 dp[x] 表示组成整数 x 所需的最少平方数个数。dp[0]=0;对每个 x>=1, 枚举不超过 x 的平方 square=j*j,最后一个加数取它时有:

\[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++ 实现

class Solution {
public:
    int numSquares(int n) {
        std::vector<int> 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 下不会溢出;算法不需要记录具体拆分方案。