---

dp专题16 完全平方数

原创 于 2024-01-19 17:37:34 发布 · 粉丝可见 · 480 阅读 · 6 · 9 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/135703601

本题链接： 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目：

思路：

这道题与 前面写的 零钱兑换 一样的思路，只不过，这里需要我们自己添加物品。

代码详解如下：

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    inline int numSquares(int& n) 
{
	vector<int>v;   // 存储完全平方数数组
	for(int i = 1;i*i <= n;++i) v.emplace_back(i*i);
 
    // 完全背包问题dp
	vector<int>dp(n + 1,INF);
	dp[0] = 0;
	
	for(int &i:v)
	{
		for(int j = i;j <= n;++j)
		{
			dp[j] = min(dp[j],dp[j - i] + 1);
		}
	}
	return dp[n];
}
};

最后提交：