题目描述：
/**
给你六种面额 1、5、10、20、50、100 元的纸币，假设每种币值的数量都足够多，
编写程序求组成N元（N为0~10000的非负整数）的不同组合的个数。
输入描述:
输入包括一个整数n(1 ≤ n ≤ 10000)
输出描述:
输出一个整数,表示不同的组合方案数
输入例子1:
1
输出例子1:
1
*/
思路如下：
dp[m][n]表示用前m中纸币可以组合出n元的组合个数
dp[m][n]=dp[m-1][n]+dp[m][n-values[m]]
values[m]表示第m种纸币的面值
base case:
dp[m][0]=1
1<=m<=MAX_M
1<=n<=MAX_N
可以采用滚动数组节省空间
下面采用滚动数组实现
代码如下：
#include<stdio.h>
#include<iostream>
#define MAX_M 6
#define MAX_N 10005
typedef long long LL;
using namespace std;
bool flag=false;
int values[MAX_M+1]={0, 1, 5, 10, 20, 50, 100};
LL dp[2][MAX_N];
int main()
{
int N;
scanf("%d", &N);
//初始化
dp[0][0]=1;
dp[1][0]=1;
for(int m=1; m<=MAX_M; m++)
{
for(int n=1; n<=N; n++)
{
dp[!flag][n]=dp[flag][n];
if(n>=values[m])
dp[!flag][n]+=dp[!flag][n-values[m]];
//printf("%lld ", dp[flag][n]);
}
//printf("\n");
flag=!flag;
}
printf("%lld", dp[flag][N]);
return 0;
}
