货币系统

题意
给定 V 种货币（单位：元），每种货币使用的次数不限。

不同种类的货币，面值可能是相同的。

现在，要你用这 V 种货币凑出 N 元钱，请问共有多少种不同的凑法。

思路：
对于题目给出的数据 我们顺次推即可得到下列这样的二维表

0 1 2 3 4 5 6 7 8 9 10

1 1 1 1 1 1 1 1 1 1 1 1

2 1 1 2 2 3 3 4 4 5 5 6

5 1 1 2 2 3 4 5 6 7 8 10

不难发现 f[2][1]=f[1][1]
f[2][2]=f[1][2]+f[1][0]
f[2][3]=f[1][3]+f[1][1]
f[2][4]=f[1][4]+f[2][2]+f[2][0]

用y总的Dp分析法即定义f[x][y]表示为前i个物品中选出体积恰好为j的方案数为多少

状态转移的时候分析：对于第i个物品有以下几种选择：

*选0个即不选第i个物品
*选1个
*选2个
....

便可推出f[i][j]=f[i][j]+f[i-1][j-k*w[i]] (k从0到j-w[i]>=0枚举即可)

本以为复杂度可能会超但是提交之后就过了很奇怪，，，感觉O(N^3),应该可以化简吧

一个本地跑可以能会超的数据
25 10000
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5
反正我的程序跑了一会才出结果。

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

typedef  long long LL;

LL f[30][N];
LL w[30];

int main()
{
	int n,v;
	cin>>n>>v;
	for(int i=1;i<=n;i++) {
		cin>>w[i];
	} 
	
	f[0][0]=1;
	
	
	for(int i=1;i<=n;i++) {
		for(int j=0;j<=v;j++) {
			for(int k=0;j-k*w[i]>=0;k++) {
				f[i][j]+=f[i-1][j-k*w[i]];
			}
		}
	}
	
	
	/*
	for(int i=1;i<=n;i++) {
		for(int j=0;j<=v;j++) {
			cout<<f[i][j]<<' ';
		} 
		puts("");
	}
	*/
	cout<<f[n][v]<<'\n';
	
	return 0;
}