/*
	Name: 
	Copyright: 
	Author: 
	Date: 31-12-14 16:51
	Description: 
	找零钱的方法数量 
描述
我们知道人民币有1、2、5、10、20、50、100这几种面值。 
现在给你n(1≤n≤250)元，让你计算换成用上面这些面额表示且总数不超过100张，共有几种。 
比如4元，能用4张1元、2张1元和1张2元、2张2元，三种表示方法。
输入
输入有多组，每组一行，为一个整合n。 
输入以0结束。
输出
输出该面额有几种表示方法。
样例输入
1
4
0
样例输出
1
3
*/

#include<stdio.h>
#include<malloc.h>
#include<math.h>

#define MAX 7

int A[MAX] = {1, 2, 5, 10, 20, 50, 100};
int count = 0;

void NumChange_1(int n, int top, int s);//回溯法 
int NumChange_2(int n); //动态规划法1 
int NumChange_3(int n); //动态规划法2 


int main()
{
    int n;
    
    scanf("%d", &n);
    while (n != 0)
    {
        count = 0;
        NumChange_1(n, 6, 0);
        printf("%d\n", count);

        printf("%d\n", NumChange_2(n));
        printf("%d\n", NumChange_3(n));
        scanf("%d", &n);
    }
    
    return 0;
}

void NumChange_1(int n, int top, int s)
{
    int i;
    
    if (n == 0)
    {
        count++;
        return ;
    }
    if (top < 0)
        return ;
    
    NumChange_1(n, top-1, s); //先不用A[top]这种货币看看
    for (i=A[top]; i<=n; i+=A[top])
    {
        if (s == 100)//总数不超过100张
            return ;
        NumChange_1(n-i, top-1, ++s);
    } 
}

int NumChange_2(int n) //动态规划法1 
{
    int f[101][251] = {1};//f[m][n]的含义为用m张钞票构成的金额为n的组合数量 
    int i, j, k, min, max;

    for (i=0; i<MAX; i++)//钞票面值 
    {
        for (j=1; j<=100; j++)//钞票张数 
        {
            min = (j > A[i]) ? j : A[i]; //为避免无效运算，给k值规定一个上限和下限 
            max = (n <= j * A[i]) ? n : j * A[i];
            for (k=min; k<=max; k++)//金额总数 
            {
                f[j][k] += f[j-1][k-A[i]];//该组合中含有一张面值为A[i]的钞票
            }
        }    
    }
    
    for(k = 0, i = 1; i <= 100; k += f[i++][n]);
    
    return k;
}

int NumChange_3(int n) //动态规划法2 
{
    int f[256][101] = {1};//f[n][m]的含义为用m张钞票构成的金额为n的组合数量 
    int i, j, k, max;

    for (i=0; i<MAX; i++)//钞票面值 
    {
        for (k=A[i]; k<=n; k++)//金额总数 
        {
            max = (k < 100) ? k : 100;
            for (j=1; j<=max; j++)//钞票张数 
                f[k][j] += f[k-A[i]][j-1];//该组合中含有一张面值为A[i]的钞票
        }
    }
        
    k = 0;
    for(i=1; i<=100; i++)
        k += f[n][i];

    return k;
}

c语言趣题之“找零钱的方法数量 ”