思路:完全背包问题。
可以首先预处理出来所谓的完全平方数有什么东西,存储到一个数组当中。
然后再进行完全背包的筛选问题。这里将个数作为价值,都是1,容积其实就是数本身。
注意:初始化的时候并不能让dp[0]=0,因为当和为零的时候是没有完全平方数可以组成的,0也不是完全平方数,0的平方没有意义。
class Solution {
public:
int numSquares(int n) {
vector<int>ans;
for(int i=1;i<=10000;i++){
int tmp=i;
for(int j=1;j<=sqrt(i);j++){
if(j*j==tmp){
ans.push_back(i);
break;
}
}
}
vector<int>dp(10010,INT_MAX);
dp[0]=0;
for(int i=0;i<ans.size();i++){
for(int j=ans[i];j<=n;j++){
dp[j]=min(dp[j],dp[j-ans[i]]+1);
}
}
return dp[n];
}
};