难度中等
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n =12输出：3 解释：12 = 4 + 4 + 4
示例 2：
输入：n =13输出：2 解释：13 = 4 + 9
class Solution {
public:
int numSquares(int n) {
vector<int> coins;
for(int t = 1;t*t <= n;t++) {
coins.emplace_back(t*t);
}
int max_s = coins.size();
vector<vector<int>> dp(max_s+1,vector<int>(n+1,INT_MAX));
dp[0][0] = 0;
for(int i = 1;i <= max_s;i++){
for(int j=0;j <=n;j++) {
dp[i][j] = dp[i-1][j];
for(int k = 1; k*coins[i-1] <=j;k++) {
if (dp[i-1][j-coins[i-1]*k] !=INT_MAX) {
dp[i][j] = min(dp[i-1][j],dp[i-1][j-coins[i-1]*k]+k);
}
}
//cout <<i <<" " << "j:" << j << "dp:" << dp[i][j] <<endl;
}
}
return dp[max_s][n];
}
};
class Solution {
public:
int numSquares(int n) {
vector<int> coins;
for(int t = 1;t*t <= n;t++) {
coins.emplace_back(t*t);
}
int max_s = coins.size();
vector<int> dp(n+1,INT_MAX);
dp[0] = 0;
for(int i = 1;i <= max_s;i++){
for(int j=0;j <=n;j++) {
if (j-coins[i-1]>=0) {
dp[j] = min(dp[j],dp[j-coins[i-1]]+1);
}
}
}
return dp[n];
}
};