完全平方数-DP

题目

给定正整数 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=end

Accepted

• 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)

这道题最快的方式是使用拉格朗日四平方定理，有兴趣的可以去看看。