动态规划-凑硬币

#include 
#include 

using namespace std;

int coinChange(vector& coins,int n)
{
    //db[i] = x 当目标金额为i时，至少还需要x枚硬币
    vector db(n+1,n+1);
    db[0] = 0;
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j < coins.size(); j++)
        {
            if(i-coins[j] < 0) continue;
            db[i] = min(db[i],1+db[i-coins[j]]);
        }
    }
    return (db[n] == n+1) ? -1:db[n];

}
int main()
{
    vector conins = {1,5,11};

    int n =coinChange(conins,15);

    cout << n << endl;
}