C代表币的种类,n代表钱数
#include<iostream>
using namespace std;
#define C 4
void main( )
{
int coin[4]={1,3,5,10};
int i,j,n=20,dp[20]={0};
for(i=1;i<20;i++) dp[i]=100;
for(i=1;i<=n;i++)
{
for(j=0;j<C;j++)
if(i-coin[j]>=0 &&dp[i-coin[j]]+1<dp[i])
dp[i]=dp[i-coin[j]]+1;}
for(i=0;i<20;i++) cout<<i<<"元,至少需要"<<dp[i]<<"枚硬币!\n";
}