用动规实现最少硬币问题
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int coins[10],T[10];
int f[20002];
int LeastCoin(int n,int m)
{
for(int i=0;i<=m;i++)
f[i]=i+1; //初始化f数组
f[0]=0;
for(int i=1;i<=n;i++)
for(int k=1;k<=coins[i];k++)
{
int tm=T[i]*k;
f[tm]=min(f[tm],f[tm-T[i]]+1);
}
if(f[m]>m)
return -1;
else
return f[m];
}