题目链接： 279. 完全平方数
题目分析：
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数：比如说1^2 = 1，2^2 = 4，3^2 = 9。1、4、9就是完全平方数。
算法原理：
从左往右开始挑完全平方数，一个数可以挑多次，挑出来的数只要等于n即可。如果对背包问题比较敏感，这就是背包问题，并且是完全背包问题。
1.状态表示
dp[i][j] 表示：从前 i 个完全平方数种挑选，总和正好等于 j，所有选法中，最少的数量
2.状态转移方程
根据最后一个位置，划分情况
不选 i^2，说明所有选法中都不包含 i^2 这个平方数，相当于从去 1 ~ i - 1 这个区间去选，就是dp[i-1][j]
选1个 i^2，然后在去1 ~ i - 1区间挑一个总和等于 j - i^2的最少数量，然后在加上选的 i^2这一个数。
同理选2个 i^2，3个 i^2…， 和上面分析一样
发现填一个状态的时候发现这个状态时候很多状态拼接而成的，这个时候我们要想到策略把这些状态用一个或者两个状态来表示。
在完全背包哪里我们已经分析过了，这里直接写。
然后从所有情况找最小值
3.初始化
- 多开一行一列
- 里面的值要保证后序的填表是正确的
- 下标的映射关系
第一列不用初始化，因为用到dp[i][j-coins[i]] 前提 j >= coins[i]，所以不会越界。我们只初始化第一行。
第一行表示完全平方数为0，当 j = 0表示总和为0，不选就行了，最少数量为0
当 j = 1、2…，完全平方数为0，根本凑不出和为 j，然后我们填dp[i][j]要最小值，为了不让这些位置得值影响填表，因此可以给0x3f3f3f3f
4.填表顺序
填dp[i][j]会用到上面和左边的值，因此从上往下填写每一行，每一行从左往右。
5.返回值
dp[i][j] 表示：从前 i 个完全平方数中挑选，总和正好等于 j，所有选法中，最少的数量，但是我们要的是从整个完全平方数种选总和正好等于n最少数量。这里有一个问题 i 取到哪里比较好呢？
我们绝对不会选一个完全平方数会比n大，所以说下标的平方应该小于等于n
所以我们最终返回的是 dp[√n][n]，同时建表的时候也应该是（√n + 1）*（n + 1）规模的。
class Solution {
public:
int numSquares(int n) {
// int m = sqrt(n);
// vector<vector<int>> dp(m + 1, vector<int>(n + 1));
// for(int j = 1; j <= n; ++j) dp[0][j] = 0x3f3f3f3f;
// for(int i = 1; i <= m; ++i)
// for(int j = 0; j <= n; ++j)
// {
// dp[i][j] = dp[i - 1][j];
// if(j >= i * i)
// dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1);
// }
// return dp[m][n];
//优化
int m = sqrt(n);
vector<int> dp(n + 1,0x3f3f3f3f);
dp[0] = 0;
for(int i = 1; i <= m; ++i)
for(int j = i * i; j <= n; ++j)
dp[j] = min(dp[j], dp[j - i * i] + 1);
return dp[n];
}
};