1.C++实现，对总金额100的最小纸币是15.
2.用递归法总金额为30就要算很久。
3.另外的数学办法可以用总金额依次对最大金额纸币求余数，直到为0.商相加为答案。如：若 {1, 2, 3, 7}为纸币金额，对于100，所需最小纸币数：100/7=14余2; 2/2 = 1余0;则纸币数为14+1=15.

// 动态规划问题
#include <iostream>
#include <string>
#include <vector>
using namespace std;

class DynamicProgramming {
 private:
  vector<int> money = {1, 2, 3, 7}; // 纸币种类

 public:
  /**
   * Description: 对于金额固定，找出最少钱币数及方式。
   * prams: amountMoney- 输入总金额
   * return: 所需最小纸币数
   */
  int findFewerstMethod(int amountMoney) {
    int c[amountMoney];
    c[0] = 0;

    int temp;
    for (unsigned int i = 1; i < amountMoney; i++) {
      // 用最大值初始化
      int tempMin = amountMoney;
      for (unsigned int j = 0; j < money.size(); j++) {
        int diff = i - money[j];
        if (0 <= diff) {
          temp = c[diff] + 1;
        } else {
          // 此情况表示该纸币无效，选择最大值。
          temp = amountMoney;
        }
        // 求出最小值
        if (temp < tempMin) {
          tempMin = temp;
        }
      }
      c[i] = tempMin;
    }

    return c[amountMoney - 1];
  }
};

// test
int main(void) {
  DynamicProgramming test;
  int res = test.findFewerstMethod(100);
  cout << res << endl;
  return 0;
}

public class Lesson10_2 {
/**    
 * 动态规划求最小钱币数    
 * @param c 用一维数组记录每一步的总金额     * @param value 用一维数组记录三种面额的纸币    
 * @return     
 */    
public static int getMinMoney(int[] c, int[] value) {
        int[] t = new int[3];        
                for (int i = 0; i < c.length; i++) {        
                       for (int j = 0; j < value.length; j++) {                
                              if (i - value[j] >= 0) {                    
                                    t[j] = c[i - value[j]] + 1;                
                               }            
                        }            
                  int min = Math.min(t[0], t[1]);            
                  min = Math.min(min, t[2]);            
                  c[i] = min;        
                }        
                return c[c.length - 1];
}    
public static void main(String[] args) {        
        int[] c = new int[100];        
        int[] value = new int[] { 2, 3, 7 };        
        System.out.println(getMinMoney(c, value)+1);    
 }
}
老师看一下代码对吗，运行结果是15

方法1，动态规划，最快。方法2递归有点慢，方法三递归，超级慢。在aim数值大于30的时候，三种写法，在我电脑速度快慢特别明显。用2元,3元,5元去找开100块，用递归方法，我的电脑要等到地老天荒O(∩_∩)O哈哈~
#include<iostream>
#include<vector>

using namespace std;

int dp_solve(int *a, int n, int aim){
    vector<vector<int>> dp(n, vector<int>(aim+1, 0));

    for(int j = 1; j <= aim; j++){
        dp[0][j] = INT_MAX;
        if(j >= a[0] && dp[0][j - a[0]] != INT_MAX)
            dp[0][j] = dp[0][j - a[0]] + 1;
    }

    for(int i = 1; i < n; i++){
        for(int j = 1; j <= aim; j++)
        {
            int tmp = INT_MAX;
            if(j - a[i] >= 0 && dp[i][j - a[i]] != INT_MAX)
                tmp = dp[i][j - a[i]] + 1;

            dp[i][j] = min(dp[i-1][j], tmp);
        }
    }

    return dp[n-1][aim] == INT_MAX ? -1 : dp[n-1][aim];
}

int min_res = INT_MAX;
void recur_solve(int *a, int n, int aim, int k){
    if(aim == 0){
        min_res = min(min_res, k);
        return;
    }
    if(aim < 0)
        return;
    for(int i = 0; i < n; i++){
        aim -= a[i];
        k++;
        recur_solve(a, n, aim, k);
        aim += a[i];
        k--;
    }
}

int min_res2 = INT_MAX;
void recur_solve2(int *a, int n, int aim, vector<int> res){
    if(aim == 0){
        int size = res.size();
        min_res2 = min(min_res2, size);
        return;
    }
    if(aim < 0)
        return;
    for(int i = 0; i < n; i++){
        res.push_back(a[i]);
        recur_solve2(a, n, aim - a[i], res);
        res.pop_back();
    }
}

int main(){
    int a[] = {2,3,7};
    int sum = 25;
    /***dp最快**/
    cout << dp_solve(a, 3, sum) << endl;

    /***这种递归有点久**/
    recur_solve(a, 3, sum, 0);
    cout << min_res << endl;

    /**这个太久了**/
    vector<int> result;
    recur_solve2(a, 3, sum, result);
    cout << min_res2 << endl;
    return 0;
}

本篇所得： 1.求解 最值可用动态规划 方法;
2.状态转移 可以把 大问题 分解为 小问题，再分解为 可以处理的问题，即 把 不可以处理的问题 分解为可以 处理的小问题（ 也为子问题）;
3.动态规划 适用于 下一个 状态与上一个状态有固定关系;
4.搜索引擎的 搜索词的查询推荐， 英文可用 编辑距离，中文 需要 转化 比 如转为英文 再使用 编辑距离;
5.从问题开始 ，初步分解 大问题为可解的子问题 为动态规划的方法，由问题 推到答案，也为反向思维法。

回答老师的问题：固定金额，找最小钱币数量，可用倒推法，总金额 减去 最大的 钱币数额 ，然后从钱币中寻找该数额，没有 再把该数额逐渐减去 大的数额，一步步分解，可得 钱币的数量，该方法是 动态规划，但不能保证寻找的是最小的数量，局部最优 不一定全局最优，如果 需要寻找全部最优 需要运用 排列和组合。

package Part01;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Lesson10_ex {
    public static void main(String[] args) {
        switchMoney(2, 3, 7, 100);
    }

    private static void switchMoney(int mz1, int mz2, int mz3, int total) {
        List<Integer[]> list = new ArrayList<Integer[]>();
        int s1 = total / mz1;
        int s2 = total / mz2 + 1;
        int s3 = total / mz3 + 1;
        for (int i = 0; i <= s1; i++) {
            for (int j = 0; j <= s2; j++) {
                for (int k = 0; k <= s3; k++) {
                    if (mz1 * i + mz2 * j + mz3 * k == 100) {
                        list.add(new Integer[] { i, j, k });
                    }
                }
            }
        }
        Integer[] result = new Integer[3];
        int min = total;
        for (Integer[] integers : list) {
            int sum = 0;
            for (Integer num : integers) {
                sum += num;
            }
            if (min > sum) {
                min = sum;
                result = integers;
            }
        }
        System.out.println("最小数：" + min);
        System.out.println(Arrays.toString(result));
    }
}

答案是15 种
private static int totalNumberForMoney(int[] moneyKind,int total){
        //初始化 c数组
        int[] c = new int[total+1];
        for(int i=1;i<c.length;i++){
            c[i] = -1;
        }
        c[0] = 0;
        for(int i=1;i<=total;i++){
             int[] data = new int[moneyKind.length];
              for(int j = 0;j<moneyKind.length;j++){
                  if((i - moneyKind[j])<0){
                      data[j]= -1;
                      continue;
                  }
                  data[j] = c[i - moneyKind[j]];
              }
              int min = min(data);
              if(min == -1){
                  continue;
              }
              c[i] = min + 1;
            System.out.println(i + "min" + c[i]);
        }
        return c[total];
    }

    private static int min(int[] data) {
        boolean flag = true;
        int min = -1;
        for(int i=0;i<data.length;i++){
            if(data[i]==-1){
                continue;
            }
            if(flag){
                min = data[i];
                flag = false;
                continue;
            }
            if(data[i]<min){
                min = data[i];
            }
        }
        return min;
    }

用python交作业
用递归来实现时，运行非常慢。用循环实现时，由于记录了每一步的计算结果，不需要重复计算，速度快很多。

递归：
import sys
def least_bills_recursion(total):
    if total == 0:
        return 0
    if total < 0:
        return sys.maxint
    min_bills = min(1 + least_bills_recursion(total-2), 1 + least_bills_recursion(total - 3),
        1 + least_bills_recursion(total-7))
    return min_bills

循环：
def least_bills_iteration(total):
    current = 0
    dp = [0] * (total + 1)
    dp[2] = 1
    dp[3] = 1
    dp[7] = 1
    for i in xrange(3, total+1, 1):
        if i >= 7:
            dp[i] = min(dp[i-2], dp[i-3], dp[i-7]) + 1
        elif i >= 3 and i < 7:
            dp[i] = min(dp[i-2], dp[i-3]) + 1
        else:
            dp[i] = dp[i-2] + 1
    return dp[total]

当总金额为100时，答案为15.

https://github.com/somenzz/geekbang/blob/master/mathOfProgramer/chapter10_dynamic_programming.py
实现了循环和递归，循环的方式快，递归的方式特别慢。
个人感觉递归是从后往前推导的，每一步的结果不论是否最优都保存在堆栈中，都占用了内存空间，算法上已经不属于动态规划。

循环的方式不论 num 有多大，仅占用了7个变量的内存空间，每一步都保留上一步的最优解，因此效率较高，而且可以方便地打印出有最小数量的组合。

循环方式的代码的输出如下：
 1 -> None
 2 -> (1, [2])
 3 -> (1, [3])
 4 -> (2, [2, 2])
 5 -> (2, [2, 3])
 6 -> (2, [3, 3])
 7 -> (1, [7])
 8 -> (3, [2, 3, 3])
 9 -> (2, [2, 7])
 10 -> (2, [3, 7])
 100 -> (15, [2, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7])

思考题编码：
public static int least_count(int num) {
        if (num < 0)
            return -1;
        int len = num;
        if (num < 9)
            len = 8;
        int[] c = new int[len + 1];
        c[0] = -1;
        c[1] = -1;
        c[2] = 1;
        c[3] = 1;
        c[4] = 2;
        c[5] = 2;
        c[6] = 2;
        c[7] = 1;
        c[8] = 3;

        if (num < 9) {
            return c[num];
        }

        for (int i = 9; i <= num; i++) {
            int a = c[i - 2] + 1;
            int b = c[i - 3] + 1;
            int min = Math.min(a, b);
            int m = c[i - 7] + 1;
            min = Math.min(min, m);
            c[i] = min;
        }

        return c[num];
    }

    public static void main(String[] args) {
        System.out.println(least_count(100));
    }

运行结果： 15

递归的写法：
这里举例了凑成11元的最少币数
import java.util.*;

public class MinCoins {
    public static int[] arr={7,3,2};
    public static int minNum=Integer.MAX_VALUE;
    public static HashMap<Integer,Integer> min_map=new HashMap<Integer,Integer>();
    public static void main(String []args) {
        System.out.println("Coins:"+Arrays.toString(arr));
        minCoins(0,11,new HashMap<Integer,Integer>());
        System.out.println("MinCoins:");
        for (Map.Entry<Integer,Integer>entry:min_map.entrySet()){
            System.out.println(entry.getKey()+":"+entry.getValue());
        }
    }
    
    public static void minCoins(int index,int aim,HashMap<Integer,Integer> map){
        if(index==arr.length||aim==0){
            if(aim==0){
                int num=0;
                for (Integer value:map.values())
                    num+=value;
                if(num<minNum) min_map=map;
            }
            return;
        }
        for(int i=0;arr[index]*i<=aim;i++){
            HashMap<Integer,Integer> new_map=(HashMap<Integer,Integer>)map.clone();
            new_map.put(arr[index],i);
            minCoins(index+1,aim-arr[index]*i,new_map);
        }
    }
}

#Python Version
def moneyCount(moneySum):
    """给定总金额和可能的钱币面额(2, 3, 7)，找出钱币数量最少的奖赏方式
    
    moneySum: 给定的总金额
    return: 最少的钱币数量
    """
    count = list(range(moneySum + 1))
    count[0] = 0
    count[2] = 1
    count[3] = 1
    count[4] = 2
    count[5] = 2
    count[6] = 2
    count[7] = 1
    count[8] = 3
    for i in range(9, moneySum + 1):
        first_append = count[i - 2] + 1
        second_append = count[i - 3] + 1
        third_append = count[i - 7] + 1
        count[i] = min(first_append, second_append, third_append)
        print(i, count[i])
    return count[moneySum]

if __name__ == '__main__':
    print(moneyCount(100))