1  2  3  4  5  6     //标号为i
1    1  1  1  1  1  1     //只用1元的表示方法
3    0  0  1  1  1  2     //使用了3元以后的新方法 d[3元][i]=d[old][i-3]
5    0  0  0  0  1  1     //使用了5元以后的新方法
old  1  1  2  2  3  4   

#include <iostream>
#include <vector>

using namespace std;

int coutNum(vector<int> vec,int num){   //vec是人民币的币值  num是要表示的钱数
	int len=vec.size();
	vector<int> temp(num,0);
	vector<vector<int> > v;       //创建二维数组
	for(int i=0;i<=len;i++)
		v.push_back(temp);
	for(int i=0;i<num;i++)        //第一行初始化为1
		v[0][i]=1;
	for(int i=1;i<len;i++){       //每一种币值开始计算
		for(int j=1;j<=num;j++){
			if(vec[i]>j)
				v[i][j-1]=0;
			else if(vec[i]==j)
				v[i][j-1]=1;
			else
				v[i][j-1]=v[len][j-vec[i]-1];
			v[len][j-1]=0;
			for(int x=0;x<=i;x++)
				v[len][j-1]+=v[x][j-1];
		}
	}
	return v[len][num-1];
}

int main(){
	int num=5;
	const int n=3;
	int a[n]={1,3,5};
	vector<int> vec(a,a+n);
	cout<<coutNum(vec,num)<<endl;

	system("pause");
}