0279. Perfect Squares¶
题目信息¶
- 题号:
0279
- 难度:
Medium
- 主题:
正整数拆分、完全平方数、最少项数
- 原题:
- 重点:
每一项必须是正整数的平方、同一平方数可以重复使用、返回组成目标和的最少项数
题目重述¶
给定正整数 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 下不会溢出;算法不需要记录具体拆分方案。