指定硬币无限个数兑换某个数

Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent.

有5种硬币，每种无限的，那么给定一个数，有多少种兑换方法呢？下一篇每种硬币不超过100个

 

 

 

 

 

 

 

 

 

 

 

#include<stdio.h>
/*
//c1是用来存放展开式的系数的，而c2则是用来计算时保存的，
//他是用下标来控制每一项的位置，比如 c2[3] 就是 x^3 的系数。
//用c1保存，然后在计算时用c2来保存变化的值。
*/

const int max=250;
int c1[max+1],c2[max+1];
int main()
{

    int n,i,j,k;
    int deta[]={1,5,10,25,50};
    while(scanf("%d",&n)!=EOF)
    {
        // 计算的方法还是模拟手动运算，一个括号一个括号的计算，
        // 从前往后
        //对于 1+x+x^2+x^3+ 他们所有的系数都是 1
        // 而 c2全部被初始化为0是因为以后要用到 c2[i] += x ;
        for(i=0;i<=n;i++)
        {
            c1[i]=1;
            c2[i]=0;
        }

        //第一层循环是一共有 n 个小括号，而刚才已经算过一个了
        //所以是从2 到 5

        for(i=2;i<=5;i++)
        {
            for(j=0;j<=n;j++)
            {
                for(k=0;k+j<=n;k+=deta[i-1])
                {
                    c2[k+j]+=c1[j];
                }
            }
            for(j=0;j<=n;j++)
            {
                c1[j]=c2[j];
                c2[j]=0;
            }
        }
       printf("%d\n",c1[n]);
    }

    return 0;

}