算法思想：
完全背包问题，求最少个数，递推公式为：
dp[j] = min(dp[j], dp[j-nums[i]] + 1)
代码：
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
//完全背包问题，
vector<int> dp(amount+1, INT_MAX-1);
dp[0]=0;
for(int i=0;i<coins.size();i++)
{
for(int j=coins[i];j<=amount;j++)
{
dp[j] = min(dp[j], dp[j-coins[i]]+1);
}
}
if( dp[amount] == INT_MAX-1)
return -1;
return dp[amount];
}
};
和上一个思想是一样的。
class Solution {
public:
int numSquares(int n) {
//找出n以内有多少个完全平方数
vector<int> nums;
for(int i=1;i<=n;i++)
{
if(i*i<=n)
{
nums.push_back(i*i);
cout<<i*i<<endl;
}
else
break;
}
vector<int> dp(n+1,INT_MAX);
dp[0]=0;
for(int i=0;i<nums.size();i++)
{
for(int j=nums[i];j<=n;j++)
{
// cout<<"dp[j]"<<dp[j]<<endl;
// cout<<"dp[j-nums[i]]+1)"<<dp[j-nums[i]]+1<<endl;
dp[j] = min(dp[j], dp[j-nums[i]]+1);
}
}
return dp[n];
}
};
