有数量不限的面值为 100 ，50 ，20 ，10 ，5 ，2 ，1 元的纸币，问要组成 N（N <= 10^6）共有多少种组合方式？
也就是这样一个问题：已知 n ，求方程1*x0+2*x1+5*x2+10*x3+20*x4+50*x5+100*x6=n的非负整数解的个数。
设 g[i][j] 表示只使用前 i 张纸币（第0张到第6张纸币面额分别为1、2、5、10、20、50
、100），可以组成 j 元的总方案数。这里 ( 0 <= i <= 6， 0 <= j <= n，n 为输入)
(1) 初始条件为 g[0][j] = 1 (0 <= j <= n)，表示只用面额为1的钱组成n元只有一
种方法
(2) 剩下的 g[i][j] = ∑ (g[i - 1][ j - money[i] * k])，其中 money[i]为第
i 张的面值， k 为使 j - money[i] * k >= 0 的所有值。
这个递推式子想通了之后，这个题目就完成了80%了，剩下的就是将这个式子用代码
实现了。(1) 式叫做边界条件，(2) 式叫做状态转移方程。
代码如下（没有按照编程规范写==，这样看容易懂一些）：
#include <stdio.h>
#define MAX 1000000
void main()
{
int money[7] = {1, 2, 5, 10, 20, 50, 100};
int i, j, n, t;
long g[7][MAX];
scanf("%d", &n);
for (i = 0; i <= n; i++)
{
g[0][i] = 1;
}
for (i = 1; i < 7; i++)
{
for (j = 0; j <= n; j++)
{
t = j;
g[i][j] = 0;
while (t >= 0)
{
g[i][j] = g[i][j] + g[i - 1][t];
t = t - money[i];
}
}
}
printf("%ld", g[6][n]);
}
这种方法的时间复杂度为O(n^2)，其实，做一个改进，可以将复杂度变为O(n)：
如果 money[i] <= j， 那么g[i][j] = g[i-1][j]，否则 g[i][j] = g[i][j-money[i]] +
g[i-1][j]，即使用大于等于一张 money[i] 面值的方案数+一张都不用的方案数即得答案
。
贴一个用这个改进的方法，按照编程规范写的代码：o(╯□╰)o
#include <stdio.h>
#define SUM_MAX 10000
#define NUM_MONEY 7
#define UINT unsigned int
#define ULONG unsigned long
void main()
{
UINT auiMoney[NUM_MONEY] = {1, 2, 5, 10, 20, 50, 100};
UINT i;
UINT j;
UINT uiSum;
ULONG aulAns[NUM_MONEY][SUM_MAX];
scanf("%d", &uiSum);
for (i = 0; i <= uiSum; i++)
{
aulAns[0][i] = 1;
}
for (i = 1; i < NUM_MONEY; i++)
{
for (j = 0; j <= uiSum; j++)
{
if (j >= auiMoney[i])
{
aulAns[i][j] = aulAns[i][j - auiMoney[i]] + aulAns[i - 1][j];
}
else
{
aulAns[i][j] = aulAns[i - 1][j];
}
}
}
printf("%ld", aulAns[NUM_MONEY - 1][uiSum]);
return;
}
复杂度瞬间降为O(n)。
-------------------------------------------
确实是简单的，LZ答案好乱，初看了一下，就是得到递推式：
f100(N) = f100(N-100) + f50(N-50) + f20(N-20) + f10(N-10) + f5(N-5) + f2(N-2) +
f1(N-1)
其中f(num)(N)就是利用小于等于num的面额组合N。
时间复杂度不是O(N)，是O(NlogN)
这种题显然用数学式推导出来的解是最快的。