EEPW论坛

这是一道比较有意思的题，在牛客网网直通BAT算法的题中看到。

这里坐下记录：

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

这题是到动态规划的问题。n

找钱的面值只有7种：1，2，5，10，20，50,100；当输入一个 n值介于某两个面值之间时，如n=25，则介于20到50之间，那么所有找钱的最大值是20；利用递归的思想，此时找钱的方法可分为两类，一类包含20面值，另一类不包含20，利用加法原理，将两类相加即可，而对于这两类还可以继续分，对于包含20的，那么面值此时变成了n-20=5;对于不包含20的，则所找到的面值最大为10块，这样递归下去；

递归公式：changeMoney(n,i)=changeMoney(n-money[i], i) +changeMoney(n, i-1);

1. #include<iostream>  

2.   

3. using namespace std;  

4.   

5. int money[] = {1,2,5,10,20,50,100};  

6.   

7. //n钱，money[index]<=n<money[index+1]  

8. int changeMoney(int n, int index)  

9. {  

10.     if (n<0 || index<0)  

11.     {  

12.         return 0;  

13.     }  

14.   

15.     if (n == 1 || n==0||index==0)  

16.     {  

17.         return 1;  

18.     }  

19.   

20.     return changeMoney(n-money[index], index)+ changeMoney(n, index-1);  

21. }  

22.   

23. int main()  

24. {  

25.     int n;  

26.     int count = sizeof(money) / sizeof(money[0]);  

27.   

28.     while (cin>>n && n!=0)  

29.     {  

30.         int index = 0;  

31.         //从后往前找到第一个小于n的钱数  

32.         for (int i=count-1; i>=0; --i)  

33.         {  

34.             if (n>=money[i])  

35.             {  

36.                 index = i;  

37.                 break;  

38.             }  

39.         }  

40.   

41.         cout << changeMoney(n, index) << endl;  

42.     }  

43.   

44.     system("pause");  

45.     return 0;  

46. }