【题目】

给定数组arr，arr中所有的值都为正数且不重复。

每个值代表一种面值的货币，每种面值的货币可以使用任意张，

再给定一个整数aim代表要找的钱数，求换钱有多少种方法。

【举例】

arr = [5, 10, 25, 1]，aim = 0。

组成0元的方法有1种，就是所有面值的货币都不用。所以返回1。

arr = [5, 10, 25, 1]，aim = 15。

组成15元的方法有6种，分别为3张5元、1张10元 + 1张5元、1张10元 + 5张1元、10张1元 + 1张5元、2张5元 + 5张1元和15张1元。所以返回6。

arr = [3, 5]，aim = 2。

任何方法都无法组成2元。所以返回0

【题解】

1、暴力解法：

使用递归，判断每种面值的钱使用不同数量的组合总数

2、使用动态规划法

【代码】

　　

1 #include 
     
        2 #include 
      
         3   4 using namespace std;  5   6 ///纯递归法  7 int process1(vector
       
        v, int index, int aim)  8 {  9     int res = 0; 10     if (index == v.size()) 11         res = aim == 0 ? 1 : 0; 12     else 13     { 14         for (int i = 0; v[index] * i <= aim; ++i) 15             res += process1(v, index + 1, aim - v[index] * i); 16     } 17     return res; 18 } 19  20 int coins1(vector
        
         v, int aim) 21 { 22     if (v.size() == 0 || aim < 0) 23         return 0; 24     return process1(v, 0, aim); 25 } 26  27 ///自顶向下的备忘录 28 int process2(vector
         
          v, int index, int aim, vector
          
           
            >dp) 29 { 30 int res = 0; 31 if (index == v.size()) 32 res = aim == 0 ? 1 : 0; 33 else 34 { 35 int val = 0; 36 for (int i = 0; v[index] * i <= aim; ++i) 37 { 38 val = dp[index + 1][aim - v[index] * i]; 39 if (val != 0) 40 res += val == -1 ? 0 : val; 41 else 42 res += process2(v, index + 1, aim - v[index] * i, dp); 43 } 44 } 45 dp[index][aim] = res == 0 ? -1 : res; 46 return res; 47 } 48 49 int coins2(vector
            
             v, int aim) 50 { 51 if (v.size() == 0 || aim < 0) 52 return 0; 53 vector
             
              
               >dp(v.size() + 1, vector
               
                (aim + 1, 0)); 54 return process2(v, 0, aim, dp); 55 } 56 57 ///自底向上法 58 59 int process3(vector
                
                 v, int aim) 60 { 61 vector
                 
                  
                   >dp(v.size(), vector
                   
                    (aim + 1, 0)); 62 for (int i = 0; i < v.size(); ++i) 63 dp[i][0] = 1; 64 for (int j = 1; v[0] * j <= aim; ++j) 65 dp[0][v[0] * j] = 1;//就是第一种面额最高能使用多少张？ 66 for(int i=1;i
                    
                     = 0; ++k) 71 num += dp[i - 1][j - v[i] * k]; 72 dp[i][j] = num; 73 } 74 75 return dp[v.size() - 1][aim]; 76 } 77 78 int process4(vector
                     
                      v, int aim) 79 { 80 vector
                      
                       
                        >dp(v.size(), vector
                        
                         (aim + 1, 0)); 81 for (int i = 0; i < v.size(); ++i) 82 dp[i][0] = 1; 83 for (int j = 1; v[0] * j <= aim; ++j) 84 dp[0][v[0] * j] = 1;//就是第一种面额最高能使用多少张？ 85 for (int i = 1; i < v.size(); ++i) 86 for (int j = 1; j <= aim; ++j) 87 { 88 dp[i][j] = dp[i - 1][j]; 89 dp[i][j] += j - v[i] >= 0 ? dp[i][j - v[i]] : 0; 90 } 91 return dp[v.size() - 1][aim]; 92 } 93 94 int process5(vector
                         
                          v, int aim) 95 { 96 vector
                          
                           dp(aim + 1, 0); 97 for (int j = 0; v[0] * j <= aim; ++j) 98 dp[v[0] * j] = 1;//就是第一种面额最高能使用多少张？ 99 for (int i = 1; i < v.size(); ++i)100 for (int j = 1; j <= aim; ++j)101 dp[j] += j - v[i] >= 0 ? dp[j - v[i]] : 0;102 103 return dp[aim];104 }105 106 int coins3(vector
                           
                            v, int aim)107 {108 if (v.size() == 0 || aim < 0)109 return 0; 110 return process3(v, aim);111 }112 113 void Test()114 {115 vector
                            
                             v;116 int aim;117 v = { 5, 10, 25, 1 };118 aim = 0;119 cout << coins1(v, aim) << endl;120 121 v = { 5, 10, 25, 1 };122 aim = 15;123 cout << coins2(v, aim) << endl;124 125 v = { 3,5 };126 aim = 2;127 cout << coins1(v, aim) << endl;128 }