动态规划状态转移表解法：

public int minCoins(int money) {
  if (money == 1 || money == 3 || money == 5) return 1;
  boolean [][] state = new boolean[money][money + 1];
  if (money >= 1) state[0][1] = true;
  if (money >= 3) state[0][3] = true;
  if (money >= 5) state[0][5] = true;
  for (int i = 1; i < money; i++) {
    for (int j = 1; j <= money; j++) {
      if (state[i - 1][j]) {
        if (j + 1 <= money) state[i][j + 1] = true;
        if (j + 3 <= money) state[i][j + 3] = true;
        if (j + 5 <= money) state[i][j + 5] = true;
        if (state[i][money]) return i + 1;
      }
    }
  }
  return money;
}

回溯算法实现矩阵最短路径会有边界问题，下面是修改后的代码。
private static int MIN_DIS = Integer.MAX_VALUE;
public static void minDisByBT(int i, int j, int[][] w, int n, int distance) {
        distance += w[i][j];
        if (i == n - 1 && j == n - 1) {
            if (distance < MIN_DIS) MIN_DIS = distance;
            return;
        }
        if (i < n - 1) {
            minDisByBT(i + 1, j, w, n, distance);
        }
        if (j < n - 1) {
            minDisByBT(i, j + 1, w, n, distance);
        }
    }

# 1. 回溯 : 太慢了
coin = 0
def minCoin(money):
    global coin
    if money == 1: return 1
    if money == 2: return 2
    if money == 3: return 1
    if money == 4: return 2
    if money == 5: return 1
# if money <= 0: return

    coin = 1 + min(minCoin(money-1) , minCoin(money-3) , minCoin(money-5))
    print(money , coin)
    return coin

print(minCoin(10))


# 2.写备忘录, 记录重复的递归项:
# 速度提升不知道几十万倍 ! 缺点就是有递归层数的限制 , 超过最大递归层数(几百?)会报错
import numpy as np
map = {} # 初始化一个 dict
coin = 0
def minCoin(money):
    global coin
    # 先查表 :
    if money in map: # 如果在 map 的第一列里面 , 说明记录过.
        return map[money] # 直接返回 minCoin
    if money == 1: return 1
    if money == 2: return 2
    if money == 3: return 1
    if money == 4: return 2
    if money == 5: return 1
# if money <= 0: return

    coin = 1 + min(minCoin(money-1) , minCoin(money-3) , minCoin(money-5))
    map[money] = coin # 放入map

    return coin
    
print(minCoin(100))
print(map)


'''

# 3.DP .
### 备忘录有了, 我们尝试根据递推公式 :
# coin = 1 + min(minCoin(money-1) , minCoin(money-3) , minCoin(money-5))
### 书写状态转移方程 :

s = {} # 设 s 为状态数组 :
s[1] ,s[2] ,s[3] ,s[4] ,s[5] = 1,2,1,2,1

def minCoinDP(money):
    for i in range(6,money+1):
        s[i] = 1+ min(s[i-1],s[i-3],s[i-5])

    return s[money]


print(minCoinDP(10000))

经过一个星期的努力，这个动态规划终于有点感觉了，今天来做题，我也来试试解这个题目，在看了第一个童鞋的解法后，感觉这个写的太死了，再就是没有反推出哪些币的组合，我就自己来实现了下！
我也想说动态规划的解，真不容易啊，我按照老师提供的方法，先使用回塑写出了暴力搜索，然后再画出了递归树，找到状态组合，然后才来写这个动态规划，感觉好复杂，不过吧，这个使用状态转移方程，我感觉更难，比这个递归还难写。。。。。。，最主要是这个状态想不到，但这个动态规划代码写完了，我又感觉能写方程了，我想哭。。。。。。。


public int countMoneyMin(int[] moneyItems, int resultMemory) {

    if (null == moneyItems || moneyItems.length < 1) {
      return -1;
    }

    if (resultMemory < 1) {
      return -1;
    }

    // 计算遍历的层数，此按最小金额来支付即为最大层数
    int levelNum = resultMemory / moneyItems[0];
    int leng = moneyItems.length;

    int[][] status = new int[levelNum][resultMemory + 1];

    // 初始化状态数组
    for (int i = 0; i < levelNum; i++) {
      for (int j = 0; j < resultMemory + 1; j++) {
        status[i][j] = -1;
      }
    }

    // 将第一层的数数据填充
    for (int i = 0; i < leng; i++) {
      status[0][moneyItems[i]] = moneyItems[i];
    }

    int minNum = -1;

    // 计算推导状态
    for (int i = 1; i < levelNum; i++) {
      // 推导出当前状态
      for (int j = 0; j < resultMemory; j++) {
        if (status[i - 1][j] != -1) {
          // 遍历元素,进行累加
          for (int k = 0; k < leng; k++) {
            if (j + moneyItems[k] <= resultMemory) {
              status[i][j + moneyItems[k]] = moneyItems[k];
            }
          }
        }

        // 找到最小的张数
        if (status[i][resultMemory] >= 0) {
          minNum = i + 1;
          break;
        }
      }

      if (minNum > 0) {
        break;
      }
    }

    int befValue = resultMemory;

    // 进行反推出，币的组合
    for (int i = minNum - 1; i >= 0; i--) {
      for (int j = resultMemory; j >= 0; j--) {
        if (j == befValue) {
          System.out.println("当前的为:" + status[i][j]);
          befValue = befValue - status[i][j];
          break;
        }
      }
    }

    return minNum;
  }

看了这一篇豁然开朗，上一篇的习题也会做了。感觉这些涉及多决策的习题基本上第一眼都能想到回溯法，但是用动态规划法就要好好想一想，关键还是老师说的动态转移方程式。我尝试用两种方法做了一遍，回溯法和动态规划法。

int minNum = Integer.MAX_VALUE;

    /**
     * 使用回溯法获取给定金额最小的硬币数量，调用时num为0
     *
     * @param coinVal
     * 硬币值数组
     * @param total
     * 指定的金额
     * @param num
     * 每个解法所得到的硬币数量
     */
    public void getLeastCoinNumByBackTracking(int[] coinVal, int total, int num) {
        if (total == 0) {
            if (num < minNum)
                minNum = num;
            return;
        }
        for (int i = 0; i < coinVal.length; i++) {
            if (total - coinVal[i] >= 0) {
                getLeastCoinNumByBackTracking(coinVal, total - coinVal[i],
                        num + 1);
            }
        }
    }

    /**
     * 使用动态规划法获取给定金额下最小的硬币数量
     *
     * @param coinVal
     * 硬币值数组
     * @param total
     * 给定金额
     * @return 给定金额下最小的硬币数量
     */
    public int getLeastCoinNumByDP(int[] coinVal, int total) {
        // coinNum存放的是每个对应金额下最少硬币的最优解
        int coinNum[] = new int[total + 1];
        coinNum[0] = 0;
        //初始化coinNum数组，硬币值数组对应的值的硬币数量都为1
        for (int i = 0; i < coinVal.length; i++) {
            coinNum[coinVal[i]] = 1;
        }
        
        for (int i = 1; i <= total; i++) {
            if (coinNum[i] == 0) {
                int minTemp = Integer.MAX_VALUE; // 获取每个i对应的最小硬币数值
                for (int j = 0; j < coinVal.length; j++) {
                    if (i - coinVal[j] > 0) {
                        int v1 = coinNum[i - coinVal[j]] + 1;
                        if (v1 < minTemp) {
                            minTemp = v1;
                        }
                    }
                }
                coinNum[i] = minTemp;
            }
        }
        return coinNum[total];
    }

我捋一下思路用 状态转移表法
1，首先这个问题适合用多阶段决策最优模型，不过唯一与前面的例子不同的是，这里的阶段不是很容易找，其实问题的期望实质上是保证走尽量少的阶段达到累计值到达期望值(9)，而我们前面接触的都是固定的阶段，所以从这一点上对动态规划的阶段概念又有了新认识
2，状态的定义，定义一个status[i][w]二维数组，i代表第i阶段，w表示第i阶段的累积值，且w不大于9.其实我把每一层的状态值定义为上一层的所有状态与本层的任一组合(1，3，5)的和这样我们就可以避免重复子结构(3->5与5->3的第二阶段的状态值都是8)的计算

import numpy as np
老师 , 那个回溯法的代码好像不太对 , 我用 python 写了一个
import sys
minDist = sys.maxsize
n = 4 # 这是个 4*4 的矩阵 .
w = np.array([[0,3,5,9],[2,1,3,4],[5,2,6,7],[6,8,4,3]])
# dist = np.zeros((4,4)) # 定义 dist(i, j) 为到达点 (i,j) 的路径长度
# dist[i, j] = w[i,j] + min(dist[i-1, j] , dist[i, j-1])

def minDistBackTrace(i, j, dist, w, n):
    global minDist
    dist += w[i][j]
    if i==n -1 and j == n-1 :
        if dist < minDist: minDist = dist
        return

    if i < n-1:
        minDistBackTrace(i + 1, j, dist, w, n)
    if j < n-1:
        minDistBackTrace(i , j + 1, dist, w, n)     

看了这么久，很少留言、很多思考题也只停留在想的层面，很少去实现。刚好有点时间，把动态规则这个思考题想了一下，顺便用Java实现出来。
思考题：如上面值{1,3,5}凑9块钱的最小张数、我们可以分成3个阶段。
第一阶段：用1块钱，那么1块钱可以有1、2、3...9张这几种可能。
第二阶段：在第一阶段的金额还有张数上增加3元的
第三阶段：在第二阶段总金额上载增加5元的。
状态转移方程:Sum(n) = Sum(n-1) + v * num ,v表示当前阶段的面值，num表示当前阶段的张数。
代码实现如下：
public class DynMoney {
    private static int minNum = Integer.MAX_VALUE;
    /**
     * Sum(n) = Sum(n-1) + v * num
     * @param sum 凑的总额
     * @param v 钱的面额
     * @return
     */
    public static int minMoney(int sum,int v[]) {
        nextStep(0, 0, 0, sum, v);
        return minNum;
    }
    /**
     * @param n 钱的张数.
     * @param c 到那个阶段
     * @param cv 凑的钱数
     * @param sum 要凑的钱的总数
     * @param v 面额
     */
    public static void nextStep(int n,int c, int cv,int sum,int v[]) {
        //金额凑够了
        if (cv == sum) {
            minNum = Math.min(minNum, n);
            return;
        }
        //或者凑到最后阶段，没凑够总金额
        if(c == v.length) {
            return;
        }
        //每个阶段，钱的张数，张数应该小与等于 凑的金额/面额
        for(int j=0; j <= sum/v[c]; j++) {
            if(cv + v[c]*j <= sum) {
                //当前阶段凑的不超额，下阶段继续凑
                nextStep(n+j, c+1,cv + v[c]*j, sum,v);
            }
        }
    }

    public static void main(String arg[]) {
        System.out.println(minMoney(8, new int[]{1,3,5}));
    }
}

思考题解答
使用回溯法（python实现）：
import sys
min_count = sys.maxsize # 用于追踪最小值

def minCoinCount(i, values, amount, ca):
    '''
    i: 硬币数量
    values: 硬币面值数组
    amount: 要凑的总价值
    ca: current amount 当前价值
    '''
    global min_count
    if ca == amount or i == amount: # 总共amount步
        if ca == amount and i < min_count:
            min_count = i
        return
        
    for v in values: # 依次考察每种币值
        if ca + v <= amount: # 保证不超总值价
            minCoinCount(i+1, values, amount, ca+v)
            
# 使用方法
values = [1,3,5]
minCoinCount(0, values, 9, 0)
print(min_count)

老师给的回溯法例子中边界的确有些问题。下面贴上修改后的实现：
  /**
   * call minDist(0, 0, a[0][0], a, a.length)
   * @param i cur row index
   * @param j cur column index
   * @param dist cur distance,start from a[0][0]
   * @param a array
   * @param n length of the input array
   */
  public static void minDistBt(int i, int j, int dist, int[][] a, int n) {
    System.out.printf("%2d %2d\n", i, j);
    if (i == n - 1 && j == n - 1) {
      if (dist < minDist)
        minDist = dist;
      return;
    }

    if (i + 1 < n)
      minDistBt(i + 1, j, dist + a[i + 1][j], a, n);

    if (j + 1 < n)
      minDistBt(i, j + 1, dist + a[i][j + 1], a, n);

  }

Go语言实现找零钱（动态规划）版本：

// value: 硬币币值, n: 硬币数量, w: 支付金额
func lfchange(value []int, n int, w int) int {
    sort.Ints(value)
    // 最小币值
    minV := value[0]
    // dp[i]表示支付金额为i需要多少个硬币
    dp := make([]int, w+1)
    for _, v := range value { // 初始化状态
        if v > w {
            break
        }
        dp[v] = 1
    }
    // 硬币数
    var count int
    for i := minV + 1; i <= w; i++ { // 动态规划方程转移
        count = 0
        for j := n - 1; j >= 0; j-- {
            if i%value[j] == 0 {
                dp[i] = i / value[j]
                break
            }
        }
        for j := minV; j < i; j++ {
            if dp[j] != 0 && dp[i-j] != 0 {
                count = dp[j] + dp[i-j]
                if count < dp[i] {
                    dp[i] = count
                }
            }
        }
    }
    return dp[w]
}

课后题答案（ts版本）：
class SortClazz {

            public static optionCell: number[] = [1, 3, 5];
            public static storeVal: { [key: number]: number } = {};

            public static getMinCount(targetVal: number): number {
                let optionCell = SortClazz.optionCell;
                if (optionCell.indexOf(targetVal) >= 0) {
                    return 1;
                }
                if (SortClazz.storeVal[targetVal]) {
                    return SortClazz.storeVal[targetVal];
                }

                let minArr: number[] = [];
                for (let i = 0, leng = optionCell.length; i < leng; ++i) {
                    let tempVal = targetVal - optionCell[i];
                    if (tempVal > 0) {
                        minArr.push(SortClazz.getMinCount(tempVal));
                    }
                }
                let minVal: number = targetVal;
                while (minArr.length > 0) {
                    minVal = Math.min(minVal, minArr.pop());
                }
                SortClazz.storeVal[targetVal] = ++minVal;
                return minVal;
            }

        }

思考题：
个人感觉使用转移方程的思路比转移表更加清晰。这里使用递归+备忘录讲一下我的思路：
凑够9元需要用最少的硬币：f(9)=min(5+f(4), 3+f(6), 1+f(8))，
f(4)=min(3+f(1), 1+f(3))，
f(6)=min(5+f(1), 3+f(3), 1+f(5))，
f(8)=min(5+f(3), 3+f(5), 1+f(7)),
f(7)=min(5+f(2), 3+f(4), 1+f(6)),
f(2)=1+f(1),

注：其中的f(1)、f(3)、f(5)可以看做是哨兵，结果都是1。