题目描述

给出N 种钱币的面值,每种钱币足够多，问要凑出 M 的钱最少要用多少枚钱币?

例如：N=4，M=40，钱币面值分别为 3 , 6 , 8 , 9 。

输入格式

第一行: 2 个整数 N 和 M ，N 范围在 [1,50]，M 范围在 [1,1000000]。

第二行：N 个整数，每个数范围在 [1,100]

输出格式

输出最少钱币数。如果没有方案，输出 -1 。

样例

2 100
5 8

14

完善程序

#include<bits/stdc++.h>
using namespace std;
int dp[1000006];
int n,m;
int a[100];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) 
	cin>>a[i];
	
	memset(dp,0x3f3f,sizeof(dp));
	dp[0]=__填空(1)__;
	
	for(int i=1;i<=n;i++)
		for(int j=a[i];__填空(2)__;j++)
			dp[j]=min(dp[j],__填空(3)__);
	
	if(dp[m]>1e9) cout<<-1;
	else cout<<dp[m];
	
	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}