这道题之前在刷代码随想录的时候做过，但是现在给忘干净了，现在甚至都不记得这是一个背包问题。。。又反过头去看代码随想录的视频才做出来的。这道题就是一个背包问题，这个问题可以抽象为：对于容量为j的背包，要计算出恰好装满这个背包的最少物品数。这道题没有排列数与组合数之分，所以先遍历背包或者先遍历物品都是可以的。接下来看动规五部曲：
1.确定dp[j]的含义:装满容量为j的背包所需要的最少物品数
2.确定递推公式:dp[j] = min(dp[j], dp[j - nums[i]]);
3.dp数组初始化:dp[0] = 0;
4.确定遍历顺序：先遍历物品或者先遍历背包都可以
5.打印数组(省略)
对于这道题而言，组成整数n的所有可能的平方数为物品，因此我们需要将1 ~ (int)sqrt(n)添加到一个数组中。然后初始化也很容易想到：当背包容量为0时，我们不需要放任何物品，因此dp[0]初始化为0，由于我们遍历的过程中，物品nums[i]可以选择放，也可以选择不放，上述两种情况对应的最少物品数分别为dp[j - nums[i]] + 1和dp[j]，我们需要取其中的最小值作为最新结果。

class Solution {
public:int numSquares(int n) {//动规五部曲//1.确定dp[j]的含义:装满容量为j的背包所需要的最少物品数//2.确定递推公式:dp[j] = min(dp[j], dp[j - coins[i]]);//3.dp数组初始化:dp[0] = 0//4.确定遍历顺序：先遍历物品或者先遍历背包都可以//5.打印数组(省略)vector<int> nums;vector<int> dp(n + 1, INT_MAX);//列出所有可以用上的完全平方数（相当于物品）for(int i = 1; i <= (int)sqrt(n); i++)nums.emplace_back(i * i);//初始化dp[0] = 0;for(int i = 0; i < nums.size(); i++){  //遍历物品for(int j = nums[i]; j <= n; j++){  //遍历背包dp[j] = min(dp[j], dp[j - nums[i]] + 1);}}return dp[n];}
};