dp专题16 完全平方数

本题链接：力扣（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];
}
};

最后提交：