本文目录 ⌄
题目
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.题解
这个问题具有最优的子结构，当前完全平方个数的最小值＝min（当前完全平方个数-完全平方数+1），写出递推方程即为numSquares(n)=min(numSquares(n-k) + 1) ∀k∈square numbers
可以观察到，当递归调用时有很多重复的子问题。当我们要计算numSquares(n)时，可能已经计算过这个值，为了避免不必要的重复计算，引入dp[n]。
自顶而下动态规划
/*
* @lc app=leetcode.cn id=279 lang=cpp
*
* [279] 完全平方数
*/
// @lc code=start
class Solution {
public:&
int foo(vector<int> &dp,int n){ //注意这里必须加上& 否则超时
if(dp[n]!=INT_MAX){
return dp[n];
}
for(int i=1;i*i<=n;i++){
dp[n]=min(dp[n],foo(dp,n-i*i)+1);
}
return dp[n];
}
int numSquares(int n) {
vector<int> dp(n+1,INT_MAX);
dp[1]=1;
dp[0]=0;
return foo(dp,n);
}
};
// @lc code=endAccepted
- 588/588 cases passed (428 ms)
- Your runtime beats 12.25 % of cpp submissions
- Your memory usage beats 46.15 % of cpp submissions (11.7 MB)
速度很慢了，还有一种动态规划的方式，递推公式相同
自底而上动态规划
/*
* @lc app=leetcode.cn id=279 lang=cpp
*
* [279] 完全平方数
*/
// @lc code=start
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1,INT_MAX);
vector<int> nums((int)sqrt(n)+1);
for(int i=1;i<nums.size();i++){
nums[i]=i*i;
}
dp[0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<nums.size();j++){
if(nums[j]<=i){
dp[i]=min(dp[i],dp[i-nums[j]]+1);
}
}
}
return dp[n];
}
};
// @lc code=end
Accepted
- 588/588 cases passed (460 ms)
- Your runtime beats 10.91 % of cpp submissions
- Your memory usage beats 88.46 % of cpp submissions (9.1 MB)
这道题最快的方式是使用拉格朗日四平方定理，有兴趣的可以去看看。