文章目录

• 前言
• 一、题目描述
• • • • 输入样例：
      • 输出样例：
• 二、DP思路
• 三、具体代码

前言

2022虎年初一，祝大家新年快乐！今天借着喜气，写一篇关于算法竞赛中非常重要的一种思想----动态规划（DP）。它主要用来解决最优解问题，而其思想核心往往是把最优解细化成许多个子问题来求解，最后在一步步的利用前面的结果递进优化得到问题的最优解。而这些子问题是前后相关的，并且非常相似，且处理方法一样。下面通过非常经典的一道例题来介绍这种算法思想。

一、题目描述

有n种硬币，面值分别为v1，v2，…，vn，数量无限。输入非负整数s，选用硬币，使其和为s。要求输出最少的硬币组合。

输入样例：

5
1 5 10 25 50
251

输出样例：

6

二、DP思路

我们可以定义一个数组，int Min[MONEY]，其中Min[i]对应着在凑够金额 i 下需要的最少硬币个数是多少，有了这个数组，我们就可以用来记录每一个数值下，硬币个数的最优解。动规一开始要进行初始化操作，思路就是先尝试用面值最小的硬币去装填Min[i]，这样得出来的解一定是硬币最多的情况。

例如：现在有（1,5,10）三种面值的硬币

那么首先用1元面值去装填，那么Min[i]等于i（Min[0]=0），这样一定不是最优解，那么把所有金额装完后，开始尝试用5元面值去装，那么在Min[1]~Min[4]仍然用1元是最优解，但是在Min[5]时，Min[5]=min（Min[5-5]+1,Min[5]）,那么Min[5]的结果显然会变为1，刚才我所用的这样一个取最小的判断过程，就是动态规划中非常重要的状态转移方程。

那么依次类推，同样是在5元面值下，Min[6]=Min[6-5]+1=2，这样最终我们就可以得到所有金额的最优解个数

三、具体代码

#include<bits/stdc++.h>
using namespace std;
int n;
int money;
int Min[1000000]; //每个金额对应最少的硬币数量
int value[10];  //定义面值数组
void solve()
{
	for(int k=0;k<=money;k++)  //初始值设为无穷大
	{
		Min[k]=INT_MAX;
	}
	Min[0]=0;
	for(int j=1;j<=n;j++)
	{
		for(int i=value[j];i<=money;i++)
		{
			Min[i]=min(Min[i],Min[i-value[j]]+1);  //比较使用value[j]这种面值的硬币后，需要的硬币数量是否减少
		}
	}
}
int main()
{
	cin>>n; //n种硬币
	for(int i=1;i<=n;i++)
	{
		cin>>value[i];
	}
	cin>>money;
	solve();
	cout<<Min[money]<<endl;
	return 0;
}