Coin Change

来源：g4g, Facebook Onsite

原帖：http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

题目：

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter. For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

代码：

 #include <iostream>  
 #include <string>  
 #include <vector>  
 using namespace std;  
   
 int changeCoins(int m, vector<int>& amount, int idx) {  
   if (idx == 0) return m % amount[idx] == 0 ? 1 : 0;  
   int count = 0;  
   for (int i = 0; i * amount[idx] <= m; ++i) {  
     count += changeCoins(m - i * amount[idx], amount, idx - 1);  
   }  
   return count;  
 }  
   
 vector<int> amount = {2, 3, 5};  
 int main() {  
   int m = 7;  
   int idx = amount.size();  
   cout << changeCoins(m, amount, idx-1);  
   return 0;  
 }  

二维dp

 int count( int S[], int m, int n )  
 {  
   int i, j, x, y;  
    
   // We need n+1 rows as the table is consturcted in bottom up manner using   
   // the base case 0 value case (n = 0)  
   int table[n+1][m];  
     
   // Fill the enteries for 0 value case (n = 0)  
   for (i=0; i<m; i++)  
     table[0][i] = 1;  
    
   // Fill rest of the table enteries in bottom up manner   
   for (i = 1; i < n+1; i++)  
   {  
     for (j = 0; j < m; j++)  
     {  
       // Count of solutions including S[j]  
       x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;  
    
       // Count of solutions excluding S[j]  
       y = (j >= 1)? table[i][j-1]: 0;  
    
       // total count  
       table[i][j] = x + y;  
     }  
   }  
   return table[n][m-1];  
 }