算法思想：
完全背包問(wèn)題，求最少個(gè)數(shù)，遞推公式為：
dp[j] = min(dp[j], dp[j-nums[i]] + 1)
代碼：
class Solution {
public:
? ? int coinChange(vector<int>& coins, int amount) {
? ? ? ? //完全背包問(wèn)題，
? ? ? ? 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];
? ? }
};
和上一個(gè)思想是一樣的肴甸。
class Solution {
public:
? ? int numSquares(int n) {
? ? ? ? //找出n以內(nèi)有多少個(gè)完全平方數(shù)
? ? ? ? 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];
? ? }
};
