[数据结构与算法]硬币找零问题-动态规划法（含思路解释，详细注释）

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;
}