找零钱有关问题

找零钱问题
求一个高效的算法。。

我们知道人民币有1、2、5、10、20、50、100这几种面值。 
现在给你n(1≤n≤250)元，让你计算换成用上面这些面额表示且总数不超过100张，共有几种。 
比如4元，能用4张1元、2张1元和1张2元、2张2元，三种表示方法。

Input 

输入有多组，每组一行，为一个整合n。 
输入以0结束。

Output 

输出该面额有几种表示方法。 



Sample Input 


1
4
0
Sample Output 


1
3

[解决办法]
貌似不一样

可以用动态规划:count[n][m]表示n元m张得组合数量,最终求的是sum(count[n][1 to m])

公式： count[n][m]=count[n-1][m-1](n>=1&&m>=1)+count[n-2][m-1](n>=2&&m>=1)+count[n-5][m-1]....+count[n-100][m-1].

count[0][m]=0,count[n][0]=0 ,差不多了....
[解决办法]
类似与01背包问题啊，看看谁还有更好的算法
[解决办法]
改了一下以前的代码，应该可以用

C# code

using System;namespace CSharpTest{    class Program    {        static int[] Items;        static long[,] Matrix;        static void Main(string[] args)        {            Items = new int[] { 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5 ,2 ,1};            int value = 10000;            Matrix = new long[value + 1, Items.Length];            Console.WriteLine(GetCount(0, value));            Console.ReadKey();        }        static long GetCount(int currentIndex, int remain)        {            //如果金额小于0,返回0种            if (remain < 0)                return 0;            //如果金额=0,或算到1元了则正好可以被兑换            if (remain == 0 || currentIndex == Items.Length - 1)                return 1;            if (Matrix[remain, currentIndex] == 0)                Matrix[remain, currentIndex] = GetCount(currentIndex + 1, remain) + GetCount(currentIndex, remain - Items[currentIndex]);            return Matrix[remain, currentIndex];        }    }}
[解决办法]
探讨

引用:
貌似不一样

可以用动态规划:count[n][m]表示n元m张得组合数量,最终求的是sum(count[n][1 to m])

公式： count[n][m]=count[n-1][m-1](n>=1&amp;amp;&amp;amp;m>=1)+count[n-2][m-1](n>=2&amp;amp;&amp;amp;m>=1)+c……

[解决办法]
这个可以用生成函数解决，例如4元的情况
（x^0+x^1+x^2+x^3+x^4+...）(x^0+x^2+x^4+...)
好像也是暴力法
[解决办法]
有点像因式分解
[解决办法]
母函数