题意

$n$ 块钱，求有多少种方式凑出来

思路

当前的组合数加上前 $w_i$（钱币面额）的组合数，再 $\mod 10^9+7$ 一下

代码

#include <bits/stdc++.h>
using namespace std;
int a[10005],w[1005];
int main(int argc, char **argv){
	int n,m;
	cin >> n >> m;
	for (int i = 1;i <= n;i++){
		cin >> w[i];
	}
	a[0] = 1;	// 边界
	// 循环的内外不要搞错！！
	for (int i = 1;i <= m;i++){	// 钱数遍历
		for (int j = 1;j <= n;j++){	// 钱币遍历
			if (i >= w[j]){
				a[i] += a[i - w[j]];	// 加上之前的钱币组合
				a[i] %= (int)1e9 + 7;	// 每次都模一下
			}
		}
	}
	cout << a[m];
	return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
int a[int(1e6)];
int money[1001];
int main()
{
	int n,w;
	cin >> n >> w;
	for (int i=0;i<n;i++){
		cin >> money[i];
	}
	sort(money,money+n); //内层循环像我这样用while的一定要加排序！！！
	a[0]=1;
	for (int i=1;i<=w;i++)
	{
		int j=0;
		while(money[j]<=i && j<n){
			a[i]+=a[i-money[j]];
			a[i]%=(int)1e9+7; 
			j++;
		}
	}
//	for (int i=1;i<w;i++){
//		cout << a[i] << endl;
//	}
	cout << a[w];
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
long long a[10000000];
long long a1[114514];
bool f(long long a,long long b){
	return a<b;
}
int main(){
	long long n,w,maxn=1e9+7; 
	cin>>w>>n;
	for(long long i=1;i<=w;i++){
		cin>>a1[i];
	}
	sort(a1,a1+w+1,f);
	a[0]=1;
	for(long long i=1;i<=n;i++){
	    for(long long j=1;j<=w;j++){
	    	if(i>=a1[j]){
	    		a[i]+=a[i-a1[j]]%maxn;
			}
		}
	}
	for(long long i=1;i<=n;i++){
		//cout<<a[i]<<" ";
	}
	cout<<a[n]%maxn;
}