leetcode 279.完全平方数

思路：完全背包问题。

可以首先预处理出来所谓的完全平方数有什么东西，存储到一个数组当中。

然后再进行完全背包的筛选问题。这里将个数作为价值，都是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];}
};