1、题目如下：
【问题描述】
给定 n 种不同面值的硬币，分别记为 c[0], c[1], c[2], … c[n]，假设每种硬币的数量是无限的。同时还有一个总金额 k，编写一个动态规划计算出最少需要几枚硬币凑出这个金额 k？
【样例输入】
12
1 2 5
【样例输出】
3
【样例说明】输入第一行为金额总数，第二行为硬币的不同面值；输出为需要的最少硬币数
2、算法思路
1、方法：动态规划法
2、dp[0]=0,从dp[1]开始，运算直至dp[MoneySum]。
3、动态转移方程：if(i-c[j]>=0) dp[i]=min(dp[i],dp[i-c[j]]+1);
注：输入数据的第二行以'\n'结尾，其中数据以空格间隔（详见代码）。
3、代码如下：
#include <bits/stdc++.h> using namespace std; #define N 10000 int MoneySum;//金额和 int c[N];//硬币金额存储数组 int dp[N];//所需最少硬币个数存储数组 int main(){ cin>>MoneySum;//输入金额和 int n=0;//记录硬币种类个数 for (int i= 0;i<=9; i++) { cin >> c[i]; n++;//硬币种类个数加1 if (getchar()=='\n') break;//输入回车，则结束 } for(int i=0;i<=MoneySum;i++){//赋初值10000 dp[i]=N; } dp[0]=0;//记得将dp[0]初始化为0，当金额为0时，所需最少金币为0 for(int i=1;i<=MoneySum;i++){ for(int j=0;j<n;j++){ if(i-c[j]>=0) dp[i]=min(dp[i],dp[i-c[j]]+1); //cout<<"dp["<<i<<"]:"<<dp[i]<<endl; } } cout<<dp[MoneySum]<<endl; return 0; }
