来自http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
对于整数N，找出N的所有零钱的表示。零钱可以用S={s1,s2,s3,..sm}表示，每种零钱的数量为无穷。请问有多少种找零的方法？
例如，
N = 4,S = {1,2,3}，有四种找零方式{1,1,1,1},{1,1,2},{2,2},{1,3},return 4
N = 10,S= {2,5,3,6} ，有5中找零方式{2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5} return 5;
============
递归方法，利用搜索树
1，找出子问题模型：为了统计所有s结果的数量，我们可以将问题分为两部分： 结果中不含有硬币sm， 结果中含有硬币sm
函数int count(int S[],int m,int n)计算结果的数量,
函数返回 S[0..m-1]组成的零钱 可以为N找零钱的 方法数
那么很显然可以等价于这两者的和 count(S,m-1,n) + count(S,m,n-S[m-1])，其中count[S,m-1,n]不包括S[m-1]这个硬币，count(S,m,n-S[m-1])包括了S[m-1]这个硬币。
==
迭代计算子问题，使用递归的方法：
代码的注释是为了求解有多少找零钱的方法，
code的方法是为了求解所有结果，打印出来
class A{
public:
///returns the count of ways we can sum s[0..m-1] coins to get sum n
void help_coinChange(vector<int>& s,int m,int n,vector<int> re){
/// if n is 0 then this is 1 solution (do not include any coin)
if(n==){
for(auto i: re){cout<<i<<" ";}cout<<"-"<<endl;
return;
}
/// if n is less than 0 then no solution exists
if(n<) return;
/// if there are no coins and n is greater than 0, there no solution exist
//if(m=0 && n>=1) return ;
if(m<=) return ;
///(i) excluding S[m-1] (ii) including S[m-1]
help_coinChange(s,m-,n,re);
re.push_back(s[m-]);
help_coinChange(s,m,n-s[m-],re);
}
void coinChange(vector<int>& coins, int amount){
vector<int> re;
help_coinChange(coins,coins.size(),amount,re);
}
};这种方法可以画成一颗DFS搜索树
例如：
c[,,],m=,n=,re=[]
/ \
c[],m=,n=,[]
/ \
c[],m=,n=,[]
/ \
c[],m=,n=,[] c[],m=,n=,[]
/ \
c[],m=,n=,[] c[],m=,n=,[,]
/ \
c[],m=,n=,[,] c[],m=,n=,[,,]
/ \
c[],m=,n=,[,,] c[],m=,n=,[,,,]
/ \
c[],m=,n=,[,,,] c[],m=1,n=0,[1,1,1,1,1]====
这么搜索，会有很多重复的路径在里面。
当然我们也可以采用BFS的方法来求解 http://bookshadow.com/weblog/2015/12/27/leetcode-coin-change/
代码在这里，
==================完全背包问题，动态规划
这个在在背包问题9讲里讲的很详细，可以google一下。
代码在这里(统计找零钱的种类数)
class A{
public:
void dp_coinChange(vector<int> & coins,int amount){
vector<int> re;
int n = amount;///
int m = coins.size();
vector<int> re1;
vector<int> re2;
///we need n+1 rows as the table is constructed in bottom up manner
/// using the base case 0 value case (n=0)
int table[n+][m];
///fill the enteries for 0 value case (n = 0)
for(int i = ;i<m;i++){
table[][i] = ;
}
///fill rest the table enteries in bottom up manner
for(int i = ;i< n+;i++){
for(int j = ;j<m;j++){
///count of solutions including S[j]
int x = (i-coins[j] >=)? table[i-coins[j]][j]:;
///count of solutions excluding S[j]
int y = (j >= )?table[i][j-]:;
///total count
table[i][j] = x+y;
}cout<<endl;
}
//return table[n][m-1];
}
};==================================
动态规划寻找零钱个数最少的解。leetecode 322
给定几个固定的面值，可以无限使用。一个目标数，要求用最少的硬币兑换这个target
解法1，如果每次走给定面值的步数，问对少走多少步能达到目标target，可以使用bfs的思路求解。
解法2，动态规划：dp[i] = min{dp[i-c1],dp[i-c2],dp[i-c3],dp[i-c4]...}+1
class Solution {
public:
int coinChange(vector<int>& coins, int amount){
///dp[i] = min{dp[i-c1],dp[i-c2],dp[i-c3],dp[i-c4]...}+1
if(amount == ) return ;
vector<int> dp(amount+,INT_MAX);
dp[] = ;
for(int i = ;i<amount+;i++){
for(int j = ;j<(int)coins.size();j++){
if(i-coins[j]>=){
dp[i] = min(dp[i],dp[i-coins[j]]);
}
}
int tmp = (dp[i]==INT_MAX)? INT_MAX: dp[i]+;
dp[i] = tmp;
}
return dp[amount]==INT_MAX? -: dp[amount];
}
};