给定大小不同币值和一定的钱求组合方法数

求方法数：
给定币值大小不同，和一定的钱
求组合方法数：
题目：
1762: Dollars

New Zealand currency consists of $100, $50, $20, $10, and $5 notes and $2, $1, 50c, 20c, 10c and 5c coins. Write a program that will determine, for any given amount, in how many ways that amount may be made up. Changing the order of listing does not increase the count. Thus 20c may be made up in 4 ways: 1 20c, 2 10c, 10c+2 5c, and 4 5c.

求的钱总数在50.00以内

本来此种类型题可以用递归做，但因为递归调用频繁，故时间耗费多，难以得出解

我苦想之后想出用空间来换取时间消除递归，用二维数组来记录。第一个下标用来表示钱数，第二个表示币种不断增多时候的方法数。然后根据钱数查找数组就行了。但是此法若数值大的话，空间恐怕申请不到，也可能数组初始化耗时多。

for(i=0;i<5001;i++)
   b[i][0]=1;
for(i=1;i<10;i++)
{
   for(j=0;j<5001;j++)
    b[j][i]=b[j][i-1];
   for(j=a[i];j<5001;j++){
    for(k=1;k<=j/a[i];k++)
     b[j][i]+=b[j-k*a[i]][i-1];
   }
}

另有光哥程序：

//动态规划
#include<stdio.h>
int table[5001] = {0};
int coins[10] = {5,10,20,50,100,200,500,1000,2000,5000};
int main()
{
int i,j;
table[0] = 1;
for(i=0;i<10;i++)
{
   for(j=coins[i];j<5001;j=j+5)
   {
    table[j] += table[j-coins[i]];
   }
}
table[0] = 0;
int temp;
float money;
while(scanf("%f",&money),money!=0.00)
{
   temp = int(money*100);
   printf("%5.2f%12d\n",money,table[temp]);
}
return 0;
}

显示%5.2中五位包括小数点