[原]动态规划

本文是数据结构与算法之美的学习笔记

动态规划比较适合用来求解最优问题，比如求最大值、最小值等等。它可以非常显著的降低时间复杂度，提高代码的执行效率。

动态规划的核心思想就是记住已经解决过的子问题，不去重复计算

0-1背包问题

对于一组重量不同且不可分割的物品，选择一些放入背包中，在不超过背包所能承受的最大重量前提下，怎么让背包中的总重量最大。

这种问题可以使用回溯算法解决代码如下

// 回溯算法实现。注意：这里把输入的变量都定义成了成员变量。
private int maxW = Integer.MIN_VALUE; // 结果放到 maxW 中
private int[] weight = {2，2，4，6，3};  // 物品重量
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
public void f(int i, int cw) { // 调用 f(0, 0)
  if (cw == w || i == n) { // cw==w 表示装满了，i==n 表示物品都考察完了
    if (cw > maxW) maxW = cw;
    return;
  }
  f(i+1, cw); // 选择不装第 i 个物品
  if (cw + weight[i] <= w) {
    f(i+1,cw + weight[i]); // 选择装第 i 个物品
  }
}

回溯算法的思想就是穷举出所有的可能的装法，然后找出满足条件的最大值，这种算法的时间复杂度比较高，是指数级别的，那有办法来降低其时间复杂度吗？

先找一下规律，比如我们有5个物品2,2,4,6,3。背包所能承受的重量是9，上面代码的步骤可以如下表示

上面的递归树中，每个物品都有放入和不放入两种状态，0代表不放入背包，1代表放入背包，一直往下递归。

从上面的递归树中我们发现图中的f(2,2)和f(3,4)被重复计算了两次，这时候我们可以吧已经计算好的f(i,cw)记录下来，当计算遇到重复的f(i,cw)的时候，就从记录中取出来直接用，就不用再递归了。如下：

private int maxW = Integer.MIN_VALUE; // 结果放到 maxW 中
private int[] weight = {2，2，4，6，3};  // 物品重量
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
private boolean[][] mem = new boolean[5][9]; // 备忘录，默认值 false
public void f(int i, int cw) { // 调用 f(0, 0)
  if (cw == w || i == n) { // cw==w 表示装满了，i==n 表示物品都考察完了
    if (cw > maxW) maxW = cw;
    return;
  }
  if (mem[i][cw]) return; // 重复状态
  mem[i][cw] = true; // 记录 (i, cw) 这个状态
  f(i+1, cw); // 选择不装第 i 个物品
  if (cw + weight[i] <= w) {
    f(i+1,cw + weight[i]); // 选择装第 i 个物品
  }
}

定义一个二维数组mem来保存计算过的节点，横坐标为物品总数，纵坐标为背包承受最大重量。

当然上面的代码只是在回溯算法的基础上加上了重复的判断，效率已经不错了，那如果使用动态规划应该怎么计算呢。

我们可以把求解的过程分成n个阶段，每个阶段都有两种选择，放进去还是不放进去，当我们执行完我们的选择之后，就会形成一种状态，，对应上面图中的每个节点（第几个物品和现在的重量）代码如下：

//weight: 物品重量，n: 物品个数，w: 背包可承载重量
public int knapsack(int[] weight, int n, int w) {
  boolean[][] states = new boolean[n][w+1]; // 默认值 false
  states[0][0] = true;  // 第一行的数据要特殊处理
  states[0][weight[0]] = true;
  for (int i = 1; i < n; ++i) { // 动态规划状态转移
    for (int j = 0; j <= w; ++j) {// 不把第 i 个物品放入背包
      if (states[i-1][j]) states[i][j] = states[i-1][j];
    }
    for (int j = 0; j <= w-weight[i]; ++j) {// 把第 i 个物品放入背包
      if (states[i-1][j]==true) states[i][j+weight[i]] = true;
    }
  }
  for (int i = w; i >= 0; --i) { // 输出结果
    if (states[n-1][i] == true) return i;
  }
  return 0;
}

1. 定义一个boolean类型的二维数组states来记录状态，数组的横坐标代表物品的个数，纵坐标为背包所能承受的重量+1（因为数组是从0开始算的所以+1），它的值代表这个状态的结果已经处理过了。
2. 第一行要做手动处理不然没法开始，第一行也就是第一个物品，它有两个状态放入还是不放入，不放入就是states[0][0] = true;放入就是 states[0][weight[0]] = true;
3. 然后从第二个开始循环，比如第二个物品它也是有放入和不放入两种选择，最终的状态会受到第一个状态的影响。
4. 如果第二个不放入，那么总重量就跟第一个的最终状态一样，所以如果这时候第一个计算过了，第二个的值就跟他一样 if (states[i-1][j]) states[i][j] = states[i-1][j] ;
5. 如果二个放入，那么如果这时候第一个已经计算过，那么第一个结果+第二个物品的重量就是当前状态的位置，把它置为true if (states[i-1][j]==true) states[i][j+weight[i]] = true; 当然这里要防止总重量超重，所以 j <= w-weight[i]
6. 依次往下循环。

总结：把问题分成多个阶段，比如上面分成物品个数n个阶段，每个阶段对应一个选择，我们记录这个阶段下我们执行了每个选择之后的状态（去掉重复的），然后通过当前状态的集合来推导下一个阶段的状态集合（比如上面的第二个物品的状态结果通过第一个物品的状态结果来获得），如此动态的往前推进。

优点：执行效率比较高

缺点：我们需要申请一个n乘以w+1的二维数组，对空间的消耗比较对，是一种空间换时间的思路。

那有没有方法可以降低空间的消耗呢，我们可以只使用一个大小为w+1的以为数组解决问题。

因为我们计算的重量肯定不能大于w,所以我们所有的计算结果都只可能是0-w中的一个，因此一个数组就可以解决，我们只需把我们计算的最终结果在数组中的位置置为true即可。

public static int knapsack2(int[] items, int n, int w) {
  boolean[] states = new boolean[w+1]; // 默认值 false
  states[0] = true;  // 第一行的数据要特殊处理
  states[items[0]] = true;
  for (int i = 1; i < n; ++i) { // 动态规划
    for (int j = w-items[i]; j >= 0; --j) {// 把第 i 个物品放入背包
      if (states[j]) states[j+items[i]] = true;
    }
  }
  for (int i = w; i >= 0; --i) { // 输出结果
    if (states[i]) return i;
  }
  return 0;
}

如果只是求最大重量，我们可以不必保存物品的编号

states表示所有当前背包可能的重量的

如果要把第i个物品放入背包，首先背包重量不能超，所以从 w-items[i] 开始递减循环找到目前背包中小于它的所有的情况加上当前的值items[i]

为了防止计算结果被覆盖，内层循环我们必须从后向前分别计算，因为数组中总是保存的当前的最优结果，而其下一个状态是依赖当前状态的。

比如目前states[2]=true,states[5]=true,如果把i放入包中，如果w[i]=1我们想要的结果应该是states[3]=true,states[6]=true。但是如果我们从前往后循环的话，states[3]=true之后，那么states[4]也会被赋值为true，states[3]这个结果影响到了后面的赋值。

OK现在给问题升级，给物品加上价值这个变量，对于一组不同重量、不同价值、不可分割的物品，我么选择把物品装入背包中，在满足背包最大重量限制的前提下，如何让背包中的总价值最大呢

我们把问题求解分成n个阶段，每个阶段的物品会有两种选择放入还是不放入，每次决策完之后，背包中的物品总重量和总价值都会有多种情况，对于i和w相同价值不同的状态点，只需要保留价值最大的那个继续往下处理即可

public static int knapsack3(int[] weight, int[] value, int n, int w) {
  int[][] states = new int[n][w+1];
  for (int i = 0; i < n; ++i) { // 初始化 states
    for (int j = 0; j < w+1; ++j) {
      states[i][j] = -1;
    }
  }
  states[0][0] = 0;
  states[0][weight[0]] = value[0];
  for (int i = 1; i < n; ++i) { // 动态规划，状态转移
    for (int j = 0; j <= w; ++j) { // 不选择第 i 个物品
      if (states[i-1][j] >= 0) states[i][j] = states[i-1][j];
    }
    for (int j = 0; j <= w-weight[i]; ++j) { // 选择第 i 个物品
      if (states[i-1][j] >= 0) {//说明计算过
        int v = states[i-1][j] + value[i];
        if (v > states[i][j+weight[i]]) {
          states[i][j+weight[i]] = v;
        }
      }
    }
  }
  // 找出最大值
  int maxvalue = -1;
  for (int j = 0; j <= w; ++j) {
    if (states[n-1][j] > maxvalue) maxvalue = states[n-1][j];
  }
  return maxvalue;
}

使用一个二维数组来保存每次决策完之后的状态，跟上面不同，这里的数组中存储的值对应物品的总价值， if (v > states[i][j+weight[i]]) 表示每一层中重复节点的值取最大的。

什么问题适合用动态规划来解决？

我们一般使用动态规划来解决最优问题，这个问题可以分成过个决策阶段，每个决策阶段都对应着一组状态，然后寻找最优的一组决策序列。

特征：

1. 最优子结构：问题的最优解包含子问题的最优解，也就是说，可以通过子问题的最优解推导出问题的最优解。后面阶段的状态可以通过前面阶段的状态推导出来。
2. 无后效性：这个有两层含义，第一层是在推导一个阶段的值的时候，我们只关心这个状态的前面的状态的值，不关系这个状态是怎么一步一步推导过来的。第二层是某个阶段的状态一旦确定，就不受之后的状态的影响。
3. 重复子问题：不同的决策序列，在达到某个相同的阶段的时候，可能会产生重复的状态。

两种动态规划的解题思路：

1. 状态转移表法

一般能用动态规划解决的问题，都能用回溯算法解决，所以我们可以先用回溯算法解决问题，然后定义状态，每个状态就是一个节点，画出对应的递归树，从递归树中看有没有重复的子问题，是怎么产生的，寻找规律。

找到重复子问题之后，我们可以通过回溯算法添加备忘录的方式来避免重复子问题，也可以通过动态规划的状态转移表法处理

先画出一个状态表，可以使用二维数组表示，每个状态有三个变量，行、列、数值。我们根据决策的先后过程，从前往后根据递推关系分阶段填充状态表中的每个状态。然后把这个填表的过程翻译成代码。

2. 状态转移方程法

我们需要分析某个问题如何通过子问题来递归求解，也就是最优子结构，根据最优子结构写出递推公式，就是状态转移方程，方程写出来代码就简单了。

例子：硬币找零

假设我们有几种不同面值的硬币V1,V2…Vn单位是元数量可以无限供应。如果我们要支付w元，求最少需要多少个硬币。

比如我们有1,3,5三个硬币coin[]={1,3,5} 要支付9元

一般情况先动态规划的问题都可以通过回溯算法解决，而回溯算法相对于动态规划稍微简单一些，所以我们先用回溯暴力解决一下。

使用回溯就是先按照有一个面值走到头，直到不满足条件，返回上一层继续递归，直到不满足在返回上一层，依次类推

int minNum = Integer.MAX_VALUE;
 //total是需要支付的总数
 //step 是步数
 public static void minCoin(int [] coins,int total,int step){
            if(total==0)
                if(step<minNum) {
                    minNum = step;
                    return;
                }
            //循环每一枚硬币放进去后其他的硬币的情况
            for (int i = 0; i < coins.length; i++) {
                if(total - coins[i]>=0){//如果当前币值小于剩余总币值就放进去
                    minCoin(coins,total-coins[i],step+1);
                }
            }
        };

然后我们从for循环第一行加一个打印日志 System.out.println("coins-"+coins[i]+"---step-"+step+"---total-"+total); 就会发现，循环的过程中有很多的重复状态。

从回溯递归上来看，我们的递归最深的层次就是：总数除以最小面值。所以使用动态规划我们可以直接循环这个最深的层次。

代码如下：

//调用之前先把数组从小到大排序 
    public static int minCoinCount(int[] coins, int total) {
        if (null == coins || coins.length < 1|| total < 1) {
            return -1;
        }
        // 计算遍历的层数，此按最小金额来支付即为最大层数
        // （调用之前先把数组排序，然后取第一个），比如全用1的话最多9层
        int levelNum = total / coins[0];

        //定义二维数组保存状态，横坐标是最大值，纵坐标是最大遍历层数，值是当前的币值
        int[][] status = new int[levelNum][total + 1];

        // 初始化状态数组
        for (int i = 0; i < levelNum; i++) {
            for (int j = 0; j < total + 1; j++) {
                status[i][j] = -1;
            }
        }
        // 将第一层的数数据填充 status[0][1]=1 status[0][3]=3 status[0][5]=5
        for (int i = 0; i < coins.length; i++) {
            status[0][coins[i]] = coins[i];
        }
        int minNum = -1;
        // 计算推导状态
        for (int i = 1; i < levelNum; i++) {
            for (int j = 0; j < total; j++) {
                //使用上一层推导当前层
                if (status[i - 1][j] != -1) {
                    // 遍历元素,进行累加(比如上层1已经放入，当前层在上层基础上在+1，+3，+5)
                    for (int k = 0; k < coins.length; k++) {
                        if (j + coins[k] <= total) {//如果超过最大值就跳过
                            status[i][j + coins[k]] = coins[k];
                        }
                    }
                }
                // 找到最小的张数（当前行的最后一列）
                if (status[i][total] >= 0) {
                    minNum = i + 1;
                    break;
                }
            }
            if (minNum > 0) {
                break;
            }
        }
        int befValue = total;

        // 进行反推出，币的组合，minNum就是当前的种类数也就是最少到第几层
        for (int i = minNum - 1; i >= 0; i--) {
            for (int j = total; j >= 0; j--) {
                if (j == befValue) {
                    System.out.println("当前的为:" + status[i][j]);
                    befValue = befValue - status[i][j];
                    break;
                }
            }
        }
        return minNum;
    }