动态规划题目

时间:2022-07-01 11:08:50

想兑换100元钱,有1,2,5,10四种钱,问总共有多少兑换方法。


下面提供两种实现方式,其中代码注释的很清楚。


关于动态规划的基本原理,参考:

http://www.cnblogs.com/sdjl/articles/1274312.html



2. 递归解法

[cpp]  view plain  copy
  1. //动态规划   
  2. #include<iostream>  
  3. using namespace std;   
  4.   
  5. const int N = 100;    
  6. int dimes[] = {1, 2, 5, 10};    
  7. int arr[N+1] = {1};    
  8.     
  9. int coinExchangeRecursion(int n, int m) //递归方式实现,更好理解  
  10. {    
  11.     if (n == 0)    //跳出递归的条件  
  12.         return 1;    
  13.     if (n < 0 || m == 0)    
  14.         return 0;    
  15.     return (coinExchangeRecursion(n, m-1) + coinExchangeRecursion(n-dimes[m-1], m));    
  16.     //分为两种情况,如果没有换当前硬币,那么是多少?加上,如果换了当前硬币,总值减少,此时又是多少种兑换方法?  
  17. }  
  18.   
  19. int main()  
  20. {  
  21.     int num=coinExchangeRecursion(N, 4);   
  22.     cout<<num<<endl;   
  23.   
  24.     int num2=coinExchange(N);   
  25.     cout<<num2<<endl;   
  26.   
  27.     return 0;   
  28.   
  29. }  




3. 非递归解法


[cpp]  view plain  copy
  1. //动态规划   
  2. #include<iostream>  
  3. using namespace std;   
  4.   
  5. const int N = 100;    
  6. int dimes[] = {1, 2, 5, 10};    
  7. int arr[N+1] = {1};    
  8.   
  9. int coinExchange(int n)   //非递归实现  
  10. {    
  11.     int i, j;    
  12.     for (i = 0; i < sizeof(dimes)/sizeof(int); i++)   //i从0 ~ 3     因为每个arr[j]都要有一次是假设兑换了dimes[i],所以我们要遍历一次  
  13.     {    
  14.         for (j = dimes[i]; j <= n; j++)     
  15.             //求,arr[j]的时候,可以看出arr[j] = arr[j] + arr[j-dimes[i]],  
  16.             //对应着上面的递归方式:arr[j]就是coinExchangeRecursion(n, m-1),  
  17.             //arr[j-dimes[i]]就是coinExchangeRecursion(n-dimes[m-1], m)  
  18.             arr[j] += arr[j-dimes[i]];    
  19.           
  20.     }    
  21.     return arr[n];    
  22. }    
  23.   
  24.   
  25. int main()  
  26. {  
  27.     int num=coinExchangeRecursion(N, 4);   
  28.     cout<<num<<endl;   
  29.   
  30.     int num2=coinExchange(N);   
  31.     cout<<num2<<endl;   
  32.   
  33.     return 0;   
  34.   
  35. }  



    大家可以看出来,递归方式求解比较便于理解。当时,我们一定也要掌握非递归方式的实现,虽然它不太好想,例如上面的


[cpp]  view plain  copy
  1. arr[j] += arr[j-dimes[i]];   


这一句。当时非递归方式的有效性是有目共睹的!