🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 关注专栏： 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

目录

🍓一、题目描述

🍓二、测试样例

🍅2.1 测试样例一

🍅2.2 测试样例二

🍓三、算法思路

🍓四、代码实现

🍓五、复杂度分析

🍅5.1 时间复杂度

🍅5.2 空间复杂度

🍓六、总结

下面来看一道完全背包算法的题目。

🍓一、题目描述

给定一个整数 n ，返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

🍓二、测试样例

🍅2.1 测试样例一

输入：n = 12

输出：3

说明：n = 12，使用三个完全平方数 4 即可组成，12 = 4 + 4 + 4

🍅2.2 测试样例二

输入：n = 13

输出：2

说明：n = 13，使用完全平方数 4 和 9 即可组成，13 = 4 + 9

🍓三、算法思路

本题主要考查完全背包算法，但是，有一点与常规的完全背包算法不同，本题中完全平方数可以看做是物品，每个完全平方数可以使用无限次，对应于物品可以使用无限次，所以需要使用完全背包算法。

但是，本题中求解的是使用最少的完全平方数，需要特殊处理一下，使用 dp 数组记录最优值。

🍓四、代码实现

代码实现如下所示：

#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;

class Solution {
public:
    int numSquares(int n) {
        if(n == 1) return n;
        int dp[n + 5];
        memset(dp, -1, sizeof(dp));
        dp[0] = 0;
        for(int i = 1; i <= sqrt(n) + 1; ++i) {
            int k = i * i;
            for(int j = k; j <= n; ++j) {
                if(dp[j - k] == -1) continue;
                if(dp[j] == -1) {
                    dp[j] = dp[j - k] + 1;
                } else {
                    dp[j] = min(dp[j], dp[j - k] + 1);
                }
            }
        }
        return dp[n];
    }
};

int main()
{
    Solution obj;
    cout<<obj.numSquares(13)<<endl;
    return 0;
}

​

图1 通过截图

🍓五、复杂度分析

🍅5.1 时间复杂度

时间复杂度为：O(n^(3/2))，其中，n 为输入的值，完全背包的容量，在上述算法中，时间主要在于两个 for 循环，两个 for 循环长度分别为 sqrt(n) 和 n，所以时间复杂度为 O(n^(3/2))。

🍅5.2 空间复杂度

空间复杂度为：O(n)，n 为完全背包的容量，使用 dp 数组记录最优值，所以空间复杂度为 O(n)。

🍓六、总结

本题主要考查完全背包算法，在理解题意的基础上，转化为完全背包算法，需要特殊处理一下最少的完全平方数的条件。

​

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 关注专栏： 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬