介绍

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

初识动态规划

通过两个非常经典的动态规划问题模型，向你展示我们为什么需要动态规划，以及动态规划解题方法是如何演化出来的。

动态规划解题思路：把问题分解为多个阶段，每个阶段对应一个决策。我们记录每一个阶段可达的状态集合（去掉重复的），然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。

0-1 背包问题（knapsack problem）

对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？这里0-1是指对于每件物品，只有不放、放两种决策。

求解方法：

• 贪心算法：不一定是最优解
• 回溯算法：穷举搜索所有可能的解、复杂度较高、是指数级别的，回溯算法求解的递归树如下图所示：假设背包的最大承载重量是 9，有 5 个不同的物品，每个物品的重量分别是 2，2，4，6，3，递归树中的每个节点表示一种状态，我们用（i, cw）来表示，其中，i 表示将要决策第几个物品是否装入背包，cw 表示当前背包中物品的总重量，第i层就可以看作是对第i个物品做决策放/不放进背包后的状态。简化求解的办法是记录重复求解的子问题，比如图中 f(2, 2) 和 f(3,4) 都被重复计算了两次。
  

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][10]; // 备忘录，默认值false，i表示将要决策第几个物品是否装入背包，j表示当前背包中物品的最大总重量，值true/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; // 重复状态，对于物品i决策后已到达过总重量cw
  mem[i][cw] = true; // 记录(i, cw)这个状态

  // 递归
  f(i+1, cw); // 选择不装第i个物品
  if (cw + weight[i] <= w) {
    f(i+1, cw + weight[i]); // 选择装第i个物品
  }
}

• 动态规划：

  • 把整个求解过程分为 n 个阶段，每个阶段会决策一个物品是否放到背包中。每个物品决策（放入或者不放入背包）完之后，背包中的物品的重量会有多种情况，也就是说，会达到多种不同的状态，对应到递归树中，就是有很多不同的节点。
  • 把每一层重复的状态（节点）合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合。我们可以通过合并每一层重复的状态，这样就保证每一层不同状态的个数都不会超过 w 个（w 表示背包的承载重量），也就是例子中的 9。于是，我们就成功避免了每层状态个数的指数级增长。
  • 用一个二维数组 states[n][w+1]，来记录每层可以达到的不同状态（从第1个物品开始决策，决策到物品i，如果可以达到重量j，那么用states[i][j]=True来表示可以达到这个状态：
    • 第 0 个（下标从 0 开始编号）物品的重量是 2，要么装入背包，要么不装入背包，决策完之后，会对应背包的两种状态，背包中物品的总重量是 0 或者 2。我们用 states[0][0]=true 和 states[0][2]=true 来表示这两种状态。
    • 第 1 个物品的重量也是 2，基于之前的背包状态，在这个物品决策完之后，不同的状态有 3 个，背包中物品总重量分别是 0(0+0)，2(0+2 or 2+0)，4(2+2)。我们用 states[1][0]=true，states[1][2]=true，states[1][4]=true 来表示这三种状态。
    • 以此类推，直到考察完所有的物品后，整个 states 状态数组就都计算好了。
    • 在最后一层，找一个值为 true 的最接近 w（这里是 9）的值，就是背包中物品总重量的最大值。
      
      

• 时间复杂度：O(2^n)

第一种写法：状态转移矩阵是二维数组

• 时间复杂度：O(n*w)
• 空间复杂度：O(n*w)

// weight:物品重量，n:物品个数，w:背包可承载重量
public int knapsack(int[] weight, int n, int w) {
  // 定义状态转移矩阵(n, w+1)，数据类型是bool，表示决策到第i个物品是否可以达到重量j这个状态（状态是指重量）
  boolean[][] states = new boolean[n][w+1]; // 默认值false，如果是true表示决策完第i个物品后、重量可以是j
  
  // 第一件物品做决策，初始化其状态
  states[0][0] = true;  // 不放
  if (weight[0] <= w) {
    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] == true) states[i][j] = states[i-1][j]; // 好像不做if判断也可以，这里是为了少做赋值操作吗
    }
    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;
}

第二种写法：状态转移矩阵是一维数组

• 时间复杂度：O(n*w)
• 空间复杂度：O(w)，减少了空间消耗

public static int knapsack2(int[] items, int n, int w) {
  // 定义状态转移矩阵(w+1,)，数据类型是bool，表示决策到第i个物品是否可以达到重量j这个状态（状态是指重量）
  boolean[] states = new boolean[w+1]; // 默认值false
  
  // 第一件物品做决策，初始化其状态
  states[0] = true;  // 放
  if (items[0] <= w) {
    states[items[0]] = true; // 不放
  }
  
  // 后面的物品逐个做决策，在前一件状态的基础上、根据放/不放来得到当前可能的状态
  for (int i = 1; i < n; ++i) { // 对第i个物品放/不放做决策
  	// 如果不放，当前状态不需要改动，所以不需要写代码
  	// 如果放的话，i的状态j（在后）是由i-1的状态j-w[i]（在前）决定的，所以在用一个数组来表示的时候，不能先修改前面的j，所以对j得从后往前改动
    for (int j = w-items[i]; j >= 0; --j) { 
      if (states[j]==true) states[j+items[i]] = true;
    }
  }
  
  // 输出结果：最后一件物品决策完之后，最大的那个状态值
  for (int i = w; i >= 0; --i) {
    if (states[i] == true) return i;
  }
  return 0;
}

0-1 背包问题升级版

之前的背包问题，只涉及背包重量和物品重量，升级版引入物品价值这一变量。对于一组不同重量、不同价值、不可分割的物品，我们选择将某些物品装入背包，在满足背包最大重量限制的前提下，背包中可装入物品的总价值最大是多少呢？

• 回溯算法：递归树如下图所示，现在我们需要 3 个变量（i, cw, cv）来表示一个状态。其中，i 表示即将要决策第 i 个物品是否装入背包，cw 表示当前背包中物品的总重量，cv 表示当前背包中物品的总价值。在递归树中，有几个节点的 i 和 cw 是完全相同的，比如 f(2,2,4) 和 f(2,2,3)。在背包中物品总重量一样的情况下，f(2,2,4) 这种状态对应的物品总价值更大，我们可以舍弃 f(2,2,3) 这种状态，只需要沿着 f(2,2,4) 这条决策路线继续往下决策就可以。也就是说，对于 (i, cw) 相同的不同状态，那我们只需要保留 cv 值最大的那个，继续递归处理，其他状态不予考虑。
  

private int maxV = Integer.MIN_VALUE; // 结果放到maxV中
private int[] items = {2，2，4，6，3};  // 物品的重量
private int[] value = {3，4，8，9，6}; // 物品的价值
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
public void f(int i, int cw, int cv) { // 调用f(0, 0, 0)
  // 终止条件
  if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了
    if (cv > maxV) maxV = cv;
    return;
  }
  // 递归
  f(i+1, cw, cv); // 选择不装第i个物品
  if (cw + weight[i] <= w) {
    f(i+1, cw+weight[i], cv+value[i]); // 选择装第i个物品
  }
}

• 动态规划：
  • 把整个求解过程分为 n 个阶段，每个阶段会决策一个物品是否放到背包中。
  • 每个阶段决策完之后，背包中的物品的总重量以及总价值，会有多种情况，也就是会达到多种不同的状态。
  • 我们用一个二维数组 states[n][w+1]，来记录每层可以达到的不同状态（不过这里数组存储的值不再是 boolean 类型的了，而是当前状态对应的最大总价值）。我们把每一层中 (i, cw) 重复的状态（节点）合并，只记录 cv 值最大的那个状态，然后基于这些状态来推导下一层的状态。

第一种写法：状态转移矩阵是二维数组

public static int knapsack3(int[] weight, int[] value, int n, int w) {
  // 定义状态转移矩阵(n, w+1)，数据类型是int，表示决策到第i个物品、重量为j的情况下，所能达到的最大价值（状态是指价值）
  int[][] states = new int[n][w+1];

  // 初始化状态转移矩阵
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < w+1; ++j) {
      states[i][j] = -1;
    }
  }

  // 对第一件物品做决策
  states[0][0] = 0; // 不放，价值为0
  if (weight[0] <= w) {
    states[0][weight[0]] = value[0]; // 放，修改对应物品i对应重量j下的价值
  }
  
  // 对后续物品做决策
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j <= w; ++j) { // 不放
      if (states[i-1][j] >= 0) states[i][j] = states[i-1][j]; // if：在之前一个物品i-1当前重量j下的最大价值states[i-1][j]基础上继续往下决策
    }
    for (int j = 0; j <= w-weight[i]; ++j) { // 放
      if (states[i-1][j] >= 0) { // if：在之前一个物品i-1当前重量j下的最大价值states[i-1][j]基础上继续往下决策
        int v = states[i-1][j] + value[i];
        if (v > states[i][j+weight[i]]) {
          states[i][j+weight[i]] = v; // 修改加入当前物品i后的状态：重量j变为j+weight[i]，价值变为max(states[i][j+weight[i]]是这个格子原来的值, states[i-1][j] + value[i]是放进来后的值) 取最大
        }
      }
    }
  }
  // 找出最大值
  int maxvalue = -1;
  for (int j = 0; j <= w; ++j) {
    if (states[n-1][j] > maxvalue) maxvalue = states[n-1][j];
  }
  return maxvalue;
}

第二种写法：状态转移矩阵是一维数组

public static int knapsack3(int[] weight, int[] value, int n, int w) {
  // 定义状态转移矩阵(w+1,)，数据类型是int，表示决策到第i个物品、重量为j的情况下，所能达到的最大价值（状态是指价值）
  int[] states = new int[w+1];

  // 初始化状态转移矩阵
  for (int j = 0; j < w+1; ++j) {
     states[j] = -1;
  }

  // 对第一件物品做决策
  states[0] = 0; // 不放，价值为0
  if (weight[0] <= w) {
    states[weight[0]] = value[0]; // 放，修改对应物品i对应重量j下的价值
  }
  
  // 对后续物品做决策
  for (int i = 1; i < n; ++i) {
  	// 不放的话，不需要改动
	// 放的话，当前重量j下的最大价值为max(states[j+weight[i]]老的值, states[j] + value[i]新的值)，老的值（在右侧）不能被覆盖，所以j要从左向右遍历
    for (int j = 0; j <= w-weight[i] ; ++j) { // 放
      states[j+weight[i]] = max(states[j+weight[i]], states[j] + value[i]); // 不确定是不是这么写！！！
    }
  }
  
  // 找出最大值
  int maxvalue = -1;
  for (int j = 0; j <= w; ++j) {
    if (states[j] > maxvalue) maxvalue = states[j];
  }
  return maxvalue;
}

双十一凑单问题：0-1背包问题的变形题

假设有一张“满 200 元减 50 元”购物券，在购物车中有 n 个（n>100）想买的商品，从里面挑一些，使得在凑够满减条件（总价>=200元）的前提下，让选出来的商品价格总和最大程度地接近200 元。这个挑的方法就可以通过动态规划来挑。

跟0-1 背包问题很像，只不过是把“重量”换成了“价格”而已：

• 购物车中有 n 个商品。我们针对每个商品都决策是否购买。
• 每次决策之后，对应不同的状态集合。
• 我们还是用一个二维数组 states[n][x]，来记录每次决策之后所有可达的状态，n表示要决策的商品数，x是决策后的价格，states[n][x]的值是bool，表示是否可达。
• 不过，这里的 x 值是多少呢？0-1 背包问题中，我们找的是小于等于 w 的最大值，x 就是背包的最大承载重量 w+1。对于这个问题来说，我们要找的是大于等于 200（满减条件）的值中最小的，所以就不能设置为 200 加 1 了。就这个实际的问题而言，如果要购买的物品的总价格超过 200 太多，比如 1000，那这个羊毛“薅”得就没有太大意义了。所以，我们可以限定 x 值为 1001。
• 不过，这个问题不仅要求大于等于 200 的总价格中的最小的，我们还要找出这个最小总价格对应都要购买哪些商品。实际上，我们可以利用 states 数组，倒推出这个被选择的商品序列。状态 (i, j) 只有可能从 (i-1, j) 或者 (i-1, j-value[i]) 两个状态推导过来。所以，我们就检查这两个状态是否是可达的，也就是 states[i-1][j]或者 states[i-1][j-value[i]]是否是 true。如果 states[i-1][j]可达，就说明我们没有选择购买第 i 个商品，如果 states[i-1][j-value[i]]可达，那就说明我们选择了购买第 i 个商品。我们从中选择一个可达的状态（如果两个都可达，就随意选择一个），然后，继续迭代地考察其他商品是否有选择购买。

// items商品价格，n商品个数, w表示满减条件，比如200
public static void double11advance(int[] items, int n, int w) {
  // 定义状态矩阵states，i为第i个商品，j为总价格为j，states[i][j]=true表示状态可达
  boolean[][] states = new boolean[n][3*w+1];//超过3倍就没有薅羊毛的价值了
  
  // 对第0个商品进行决策
  states[0][0] = true;  // 不买
  if (items[0] <= 3*w) {
    states[0][items[0]] = true; // 买
  }

  // 对后续物品进行决策
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j <= 3*w; ++j) {// 不购买第i个商品
      if (states[i-1][j] == true) states[i][j] = states[i-1][j];
    }
    for (int j = 0; j <= 3*w-items[i]; ++j) {// 购买第i个商品
      if (states[i-1][j] == true) states[i][j+items[i]] = true;
    }
  }

  // 找到满足价格条件的那个可达价格
  int j;
  for (j = w; j < 3*w+1; ++j) { 
    if (states[n-1][j] == true) break; // 输出结果大于等于w的最小值
  }
  if (j == 3*w+1) return; // 没有可行解

  // 利用 states 数组，倒推出这个被选择的商品序列：只有(i-1, j-value[i])和(i-1, j)两种前序可能
  for (int i = n-1; i >= 1; --i) { // i表示二维数组中的行，j表示列
    if(j-items[i] >= 0 && states[i-1][j-items[i]] == true) { // (i-1, j-value[i]) 
      System.out.print(items[i] + " ");
      j = j - items[i]; 
    } // else 没有购买这个商品，j不变。// (i-1, j)
  }
  if (j != 0) System.out.print(items[0]);
}

课后题

假设你站在第一层，往下移动，我们把移动到最底层所经过的所有数字之和，定义为路径的长度。请你编程求出从最高层移动到最底层的最短路径长度。

思路：

• 递归树
  

• 二维状态转移表、填表过程
  

• 动态规划实现代码（状态转移表法填表过程翻译成代码）：

int[][] matrix = {{5},{7,8},{2,3,4},{4,9,6,1},{2,7,9,4,5}};

public int yanghuiTriangle(int[][] matrix) {
    int[][] state = new int[matrix.length][matrix.length];
    state[0][0] = matrix[0][0];
    for (int i = 1; i < matrix.length; i++) {
        for (int j = 0; j < matrix[i].length; j++) {
            if (j == 0) state[i][j] = state[i - 1][j] + matrix[i][j];
            else if (j == matrix[i].length - 1) state[i][j] = state[i - 1][j - 1] + matrix[i][j];
            else {
                int top1 = state[i - 1][j - 1];
                int top2 = state[i - 1][j];
                state[i][j] = Math.min(top1, top2) + matrix[i][j];
            }
        }
    }
    int minDis = Integer.MAX_VALUE;
    for (int i = 0; i < matrix[matrix.length - 1].length; i++) {
        int distance = state[matrix.length - 1][i];
        if (distance < minDis) minDis = distance;
    }
    return minDis;
}

动态规划理论

一、解决什么样的问题：一个模型&三个特征

一个模型

动态规划适合解决的问题的模型是“多阶段决策最优解模型”：

• 一般是用动态规划来解决最优问题
• 而解决问题的过程，需要经历多个决策阶段
• 每个决策阶段都对应着一组状态
• 然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值

三个特征

1. 最优子结构

最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。

2. 无后效性

无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

3. 重复子问题

这个概念比较好理解。前面一节，我已经多次提过。如果用一句话概括一下，那就是，不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

举例说明：矩阵对角最短路径

假设我们有一个 n 乘以 n 的矩阵 w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角，终止位置在右下角。我们将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角，会有很多不同的路径可以走。我们把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢？

• 是否符合“一个模型”？
  • 求解最优问题
  • 从 (0, 0) 走到 (n-1, n-1)，总共要走 2*(n-1) 步，也就对应着 2*(n-1) 个阶段，每个阶段都有向右走或者向下走两种决策 -> 多个决策阶段
  • 每个决策阶段都会对应一组状态
  • 我们把状态定义为 min_dist(i, j)，其中 i 表示行，j 表示列，min_dist 表达式的值表示从 (0, 0) 到达 (i, j) 的最短路径长度，也即寻找一组决策序列，产生最优解。

所以，这个问题是一个多阶段决策最优解问题，符合动态规划的模型。

• 是否符合“三个特征”？
  • 最优子结构：我们把从起始位置 (0, 0) 到 (i, j) 的最小路径，记作 min_dist(i, j)。因为我们只能往右或往下移动，所以，我们只有可能从 (i, j-1) 或者 (i-1, j) 两个位置到达 (i, j)。也就是说，到达 (i, j) 的最短路径要么经过 (i, j-1)，要么经过 (i-1, j)，而且到达 (i, j) 的最短路径肯定包含到达这两个位置的最短路径之一。换句话说就是，min_dist(i, j) 可以通过 min_dist(i, j-1) 和 min_dist(i-1, j) 两个状态推导出来。这就说明，这个问题符合“最优子结构”。
  • 无后效性：如果我们走到 (i, j) 这个位置，我们只能通过 (i-1, j)，(i, j-1) 这两个位置移动过来，也就是说，我们想要计算 (i, j) 位置对应的状态，只需要关心 (i-1, j)，(i, j-1) 两个位置对应的状态，并不关心棋子是通过什么样的路线到达这两个位置的。而且，我们仅仅允许往下和往右移动，不允许后退，所以，前面阶段的状态确定之后，不会被后面阶段的决策所改变，所以，这个问题符合“无后效性”这一特征。
  • 重复子问题：画一下递归树，就会发现，递归树中有重复的节点。重复的节点表示，从左上角到节点对应的位置，有多种路线。

二、解题思路

解决动态规划问题一般有两种思路：状态转移表法、状态转移方程法。 不是每个问题都同时适合这两种解题思路，有的问题可能用第一种思路更清晰，而有的问题可能用第二种思路更清晰，所以，你要结合具体的题目来看，到底选择用哪种解题思路。

1. 状态转移表法：回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码

一般能用动态规划解决的问题，都可以使用回溯算法的暴力搜索解决。所以，当我们拿到问题的时候，我们可以先用简单的回溯算法解决，然后定义状态，每个状态表示一个节点，然后对应画出递归树。从递归树中，我们很容易可以看出来，是否存在重复子问题，以及重复子问题是如何产生的。以此来寻找规律，看是否能用动态规划解决。 找到重复子问题之后，接下来，我们有两种处理思路，第一种是直接用回溯加“备忘录”的方法，来避免重复子问题，从执行效率上来讲，这跟动态规划的解决思路没有差别；第二种是使用动态规划的解决方法，状态转移表法。

状态表一般都是二维的，所以你可以把它想象成二维数组。其中，每个状态包含三个变量，行、列、数组值。我们根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。最后，我们将这个递推填表的过程，翻译成代码，就是动态规划代码了。

举例说明

对于之前的矩阵对角最短路径例子，

第一步：写出回溯代码

private int minDist = Integer.MAX_VALUE; // 全局变量或者成员变量

// 调用方式：minDistBacktracing(0, 0, 0, w, n);
public void minDistBT(int i, int j, int dist, int[][] w, int n) {
  // dist: 到达第(i,j)个元素之前的路径长度
	
  // 终止条件：到达(n,n)之前（也即到达(n-1, n-1))
  if (i == n && j == n) {
    if (dist < minDist) minDist = dist; // 整体的最短路径，就是当前路径(终止条件所处的状态)中最短的
    return;
  }
  if (i < n) { // 往下走，更新i=i+1, j=j
    minDistBT(i + 1, j, dist+w[i][j], w, n);
  }
  if (j < n) { // 往右走，更新i=i, j=j+1
    minDistBT(i, j + 1, dist+w[i][j], w, n);
  }
}

第二步：画出递归树，以此来寻找重复子问题。
在递归树中，一个状态（也就是一个节点）包含三个变量 (i, j, dist)，其中 i，j 分别表示行和列，dist 表示从起点到达 (i, j) 的路径长度。从图中，我们看出，尽管 (i, j, dist) 不存在重复的，但是 (i, j) 重复的有很多。对于 (i, j) 重复的节点，我们只需要选择 dist 最小的节点，继续递归求解，其他节点就可以舍弃了。

第三步：画出一个二维状态表，填表，翻译成代码。
表中的行、列表示棋子所在的位置，表中的数值表示从起点到这个位置的最短路径。我们按照决策过程，通过不断状态递推演进，将状态表填好。为了方便代码实现，我们按行来进行依次填充。

public int minDistDP(int[][] matrix, int n) {
  int[][] states = new int[n][n];
  int sum = 0;
  for (int j = 0; j < n; ++j) { // 初始化states的第一行数据
    sum += matrix[0][j];
    states[0][j] = sum;
  }
  sum = 0;
  for (int i = 0; i < n; ++i) { // 初始化states的第一列数据
    sum += matrix[i][0];
    states[i][0] = sum;
  }
  for (int i = 1; i < n; ++i) {
    for (int j = 1; j < n; ++j) {
      states[i][j] = 
            matrix[i][j] + Math.min(states[i][j-1], states[i-1][j]);
    }
  }
  return states[n-1][n-1];
}

2. 状态转移方程法：找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码

状态转移方程法有点类似递归的解题思路。我们需要分析，某个问题如何通过子问题来递归求解，也就是所谓的最优子结构。根据最优子结构，写出递归公式，也就是所谓的状态转移方程，是f(n)=xxxf(n-1)，有了状态转移方程，代码实现就非常简单了。一般情况下，我们有两种代码实现方法，一种是递归（加“备忘录”），另一种是迭代。

举例说明

对于之前的矩阵对角最短路径例子，状态转移方程为：

min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))

采用递归加备忘录的实现：

private int[][] matrix = 
         {{1，3，5，9}, {2，1，3，4}，{5，2，6，7}，{6，8，4，3}};
private int n = 4;
private int[][] mem = new int[4][4];

public int minDist(int i, int j) {
  // 终止条件
  if (i == 0 && j == 0) return matrix[0][0];
  if (mem[i][j] > 0) return mem[i][j]; // 已经加进过备忘录了的，就不需要再递归了
  
  // 递归
  int minLeft = Integer.MAX_VALUE;
  if (j-1 >= 0) {
    minLeft = minDist(i, j-1);
  }
  int minUp = Integer.MAX_VALUE;
  if (i-1 >= 0) {
    minUp = minDist(i-1, j);
  }
  int currMinDist = matrix[i][j] + Math.min(minLeft, minUp);
  
  // 递归结束时结果加进备忘录
  mem[i][j] = currMinDist;
  return currMinDist;
}

// 调用minDist(n-1, n-1); 

三、算法思想对比：贪心、分治、回溯、动态规划

算法思想	解决的问题	做法	优缺点
贪心	多阶段决策最优解模型。需要满足三个条件，最优子结构、无后效性和贪心选择性（通过局部最优的选择，能产生全局的最优选择）
分治	（非多阶段）最优解模型。要求分割成的子问题，不能有重复子问题
回溯	多阶段决策最优解模型。基本上能用的动态规划、贪心解决的问题，都可以用回溯算法解决	穷举搜索	复杂度高、是指数级的，对于大规模数据执行效率低
动态规划	多阶段决策最优解模型。需要满足三个特征，最优子结构、无后效性和重复子问题	状态转移表法、状态转移方程法

多阶段决策最优解模型解题思路

1. 回溯：定义阶段、状态，画出递归树，用回溯，穷举所有的状态，求最优 -> 指数复杂度
2. 回溯+备忘录：如果不存在重复子问题，那1就是最好的解决方法；如果递归树存在重复状态，那我们就可以用回溯+备忘录来解决，用备忘录记住最优子状态，无需后续的递归 -> 和3有差不多的复杂度。另外，如果递归树存在重复状态，也可以考虑用能否用动态规划来解决，见3、4。
3. 动态规划解题思路一状态转移表法：定义二维状态转移表，初始化表边界，按状态转移逻辑填表，和2有差不多的复杂度 -> 大部分状态表都是二维的，但是如果问题的状态比较复杂，需要很多变量来表示，那对应的状态表可能就是高维的，比如三维、四维。那这个时候，我们就不适合用状态转移表法来解决了。一方面是因为高维状态转移表不好画图表示，另一方面是因为人脑确实很不擅长思考高维的东西。
4. 动态规划解题思路二状态转移方程法：找出最优子结构的递推公式（也即状态转移方程）f(n)=xxxf(n-1)，可以通过递归或迭代两种方法来进行代码实现。

回溯是从0列举到n，调用的时候调用f(0)；
递归是n由n-1推出，调用的时候调用f(n)。

课后题

硬币找零问题，我们在贪心算法那一节中讲过一次。我们今天来看一个新的硬币找零问题。假设我们有几种不同币值的硬币 v1，v2，……，vn（单位是元）。如果我们要支付 w 元，求最少需要多少个硬币。比如，我们有 3 种不同的硬币，1 元、3 元、5 元，我们要支付 9 元，最少需要 3 个硬币（3 个 3 元的硬币）。

### 递推公式（状态转移方程）:
#  coin = 1 + min(minCoin(money-1) , minCoin(money-3) , minCoin(money-5))

s = {} 
// 看成走台阶问题，每步可以跨1、3、5级台阶，所以前5级台阶的走法数量要预先初始化下
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): // 状态转移方程法的迭代递推写法，从6元开始是因为
        s[i] = 1 + min(s[i-1],s[i-3],s[i-5])
    return s[money]

// 要支付10000元最少需要的硬币个数
print(minCoinDP(10000))

动态规划实战

拼写纠错实际上是求字符串相似度，比如可以用 编辑距离（Edit Distance） 来衡量。编辑距离指的就是，将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。编辑距离越大，说明两个字符串的相似程度越小；相反，编辑距离就越小，说明两个字符串的相似程度越大。对于两个完全相同的字符串来说，编辑距离就是 0。

根据所包含的编辑操作种类的不同，编辑距离有多种不同的计算方式，比较著名的有 莱文斯坦距离（Levenshtein distance） 和 最长公共子序列长度（Longest common subsequence length）。其中，莱文斯坦距离允许增加、删除、替换字符这三个编辑操作，最长公共子序列长度只允许增加、删除字符这两个编辑操作。

• 最长公共子序列（Longest common subsequence）：可不连续
• 最长公共子串（Longest common substring）：必须连续

一、求莱文斯坦距离

这个问题是求把一个字符串变成另一个字符串，需要的最少编辑次数。整个求解过程，涉及多个决策阶段，我们需要依次考察一个字符串中的每个字符，跟另一个字符串中的字符是否匹配，匹配的话如何处理，不匹配的话又如何处理。所以，这个问题符合多阶段决策最优解模型。

• 回溯做法：
  • 如果 a[i]与 b[j]匹配，我们递归考察 a[i+1]和 b[j+1]；
  • 如果 a[i]与 b[j]不匹配，那我们有多种处理方式可选：
    • 可以删除 a[i]，然后递归考察 a[i+1]和 b[j]（删除后为什么不是a[i]和b[j]？删除不是真的从字符串里删除，是想象中的删除）；
    • 可以删除 b[j]，然后递归考察 a[i]和 b[j+1]；
    • 可以在 a[i]前面添加一个跟 b[j]相同的字符，然后递归考察 a[i]和 b[j+1]（为什么不是a[i+1]和 b[j+1] -> 因为这里的添加并不是真的在字符串里添加，而是假设的处理方式，因为最后只需要找出编辑距离即可）;
    • 可以在 b[j]前面添加一个跟 a[i]相同的字符，然后递归考察 a[i+1]和 b[j]（为什么不是a[i+1]和 b[j+1] -> 原因同上）；
    • 可以将 a[i]替换成 b[j]，或者将 b[j]替换成 a[i]，然后递归考察 a[i+1]和 b[j+1]。

// 回溯写法
private char[] a = "mitcmu".toCharArray();
private char[] b = "mtacnu".toCharArray();
private int n = 6;
private int m = 6;
private int minDist = Integer.MAX_VALUE; // 存储结果

// 调用方式 lwstBT(0, 0, 0);
public lwstBT(int i, int j, int edist) {
  // 终止条件：一个字符串访问完
  if (i == n || j == m) {
    if (i < n) edist += (n-i);
    if (j < m) edist += (m - j);
    if (edist < minDist) minDist = edist; // 返回访问完成后最小的那个edist
    return;
  }
  
  // 递归
  if (a[i] == b[j]) { // 两个字符匹配，edist不变
    lwstBT(i+1, j+1, edist);
  } else { // 两个字符不匹配，edist + 1
    lwstBT(i + 1, j, edist + 1); // 删除a[i]或者b[j]前添加一个字符
    lwstBT(i, j + 1, edist + 1); // 删除b[j]或者a[i]前添加一个字符
    lwstBT(i + 1, j + 1, edist + 1); // 将a[i]和b[j]替换为相同字符
  }
}

• 递归树：根据上述回溯算法的代码实现，我们可以画出递归树（边上的+(i,j,e)即递归调用lwstBT时三个参数分别加多少），看是否存在重复子问题。
  
  在递归树中，每个节点代表一个状态，状态包含三个变量 (i, j, edist)，其中，edist 表示处理到 a[i]和 b[j]时，已经执行的编辑操作的次数。可以看到，(i, j) 两个变量重复的节点很多，比如 (3, 2) 和 (2, 3)。对于 (i, j) 相同的节点，我们只需要保留 edist 最小的，继续递归处理就可以了，剩下的节点都可以舍弃。所以，状态就从 (i, j, edist) 变成了 (i, j, min_edist)，其中 min_edist 表示处理到 a[i]和 b[j]，已经执行的最少编辑次数。

• 动态规划：

  • 找出状态转移关系
    这个问题的状态转移方式，要比之前两节课中讲到的例子都要复杂很多。上一节我们讲的矩阵最短路径问题中，到达状态 (i, j) 只能通过 (i-1, j) 或 (i, j-1) 两个状态转移过来，而今天这个问题，状态 (i, j) 可能从 (i-1, j)，(i, j-1)，(i-1, j-1) 三个状态中的任意一个转移过来。
    把状态转移的过程，用公式写出来，这就是我们前面讲的状态转移方程：

    如果：a[i]!=b[j]，那么：min_edist(i, j)就等于：
    min(min_edist(i-1,j)+1, min_edist(i,j-1)+1, min_edist(i-1,j-1)+1)

    如果：a[i]==b[j]，那么：min_edist(i, j)就等于：（是上图里面or的那个支路）
    min(min_edist(i-1,j)+1, min_edist(i,j-1)+1，min_edist(i-1,j-1))

  • 定义二维状态转移表、填表

  • 把填表过程翻译成代码：状态转移表法

public int lwstDP(char[] a, int n, char[] b, int m) {
  int[][] minDist = new int[n][m];
  // 对第一行初始化，相当于求解a[0]和b在所有位置的最小编辑距离，那么对于b第一个位置，如果和a[0]相同则为0，不同则为1。对于第j个位置的元素，如果和a[0]相同，直接等于j就行，为什么呢？因为直接把前面j-1个位置的元素删除就行，对应的编辑距离就是j（因为下标是从0开始的）
  for (int j = 0; j < m; ++j) { // 初始化第0行:a[0..0]与b[0..j]的编辑距离
    if (a[0] == b[j]) minDist[0][j] = j; // a[0]=b[j]，编辑距离从j起算？？？
    else if (j != 0) minDist[0][j] = minDist[0][j-1]+1; // a[0]!=b[j] && j!=0
    else minDist[0][j] = 1; // a[0]!=b[0]
  }
  for (int i = 0; i < n; ++i) { // 初始化第0列:a[0..i]与b[0..0]的编辑距离
    if (a[i] == b[0]) minDist[i][0] = i; // ？？？
    else if (i != 0) minDist[i][0] = minDist[i-1][0]+1;
    else minDist[i][0] = 1;
  }
  for (int i = 1; i < n; ++i) { // 按行填表
    for (int j = 1; j < m; ++j) {
      if (a[i] == b[j]) minDist[i][j] = min(
          minDist[i-1][j]+1, minDist[i][j-1]+1, minDist[i-1][j-1]);
      else minDist[i][j] = min(
          minDist[i-1][j]+1, minDist[i][j-1]+1, minDist[i-1][j-1]+1);
    }
  }
  return minDist[n-1][m-1];
}

private int min(int x, int y, int z) {
  int minv = Integer.MAX_VALUE;
  if (x < minv) minv = x;
  if (y < minv) minv = y;
  if (z < minv) minv = z;
  return minv;
}

二、求最长公共子序列长度

针对这个问题，直接定义状态，然后写状态转移方程。

每个状态还是包括三个变量 (i, j, max_lcs)，max_lcs 表示 a[0…i]和 b[0…j]的最长公共子串长度。那 (i, j) 这个状态都是由哪些状态转移过来的呢？

我们先来看回溯的处理思路（由n-1到什么状态？）：

• 我们从 a[0]和 b[0]开始，依次考察两个字符串中的字符是否匹配。
• 如果 a[i]与 b[j]互相匹配，我们将最大公共子串长度加一，并且继续考察 a[i+1]和 b[j+1]。
• 如果 a[i]与 b[j]不匹配，最长公共子串长度不变，这个时候，有两个不同的决策路线：
  • 删除 a[i]，或者在 b[j]前面加上一个字符 a[i]，然后继续考察 a[i+1]和 b[j]；
  • 删除 b[j]，或者在 a[i]前面加上一个字符 b[j]，然后继续考察 a[i]和 b[j+1]。

反过来（怎么由前序状态到n？）也就是说，如果我们要求 a[0…i]和 b[0…j]的最长公共长度 max_lcs(i, j)，我们只有可能通过下面三个状态转移过来：

• (i-1, j-1, max_lcs)，其中 max_lcs 表示 a[0…i-1]和 b[0…j-1]的最长公共子串长度；
• (i-1, j, max_lcs)，其中 max_lcs 表示 a[0…i-1]和 b[0…j]的最长公共子串长度；
• (i, j-1, max_lcs)，其中 max_lcs 表示 a[0…i]和 b[0…j-1]的最长公共子串长度。

如果我们把这个转移过程，用状态转移方程写出来，就是下面这个样子：

如果：a[i]==b[j]，那么：max_lcs(i, j)就等于：
max(max_lcs(i-1,j-1)+1, max_lcs(i-1, j), max_lcs(i, j-1))

如果：a[i]!=b[j]，那么：max_lcs(i, j)就等于：
max(max_lcs(i-1,j-1), max_lcs(i-1, j), max_lcs(i, j-1))

public int lcs(char[] a, int n, char[] b, int m) {
  int[][] maxlcs = new int[n][m];
  for (int j = 0; j < m; ++j) {//初始化第0行：a[0..0]与b[0..j]的maxlcs
    if (a[0] == b[j]) maxlcs[0][j] = 1; // a[0]=b[j]，公共子序列长度从1起算 ？？？
    else if (j != 0) maxlcs[0][j] = maxlcs[0][j-1]; // a[0]!=b[j] && j>0
    else maxlcs[0][j] = 0; // a[0]!=b[0]
  }
  for (int i = 0; i < n; ++i) {//初始化第0列：a[0..i]与b[0..0]的maxlcs
    if (a[i] == b[0]) maxlcs[i][0] = 1;
    else if (i != 0) maxlcs[i][0] = maxlcs[i-1][0];
    else maxlcs[i][0] = 0;
  }
  for (int i = 1; i < n; ++i) { // 填表
    for (int j = 1; j < m; ++j) {
      if (a[i] == b[j]) maxlcs[i][j] = max(
          maxlcs[i-1][j], maxlcs[i][j-1], maxlcs[i-1][j-1]+1);
      else maxlcs[i][j] = max(
          maxlcs[i-1][j], maxlcs[i][j-1], maxlcs[i-1][j-1]);
    }
  }
  return maxlcs[n-1][m-1];
}

private int max(int x, int y, int z) {
  int maxv = Integer.MIN_VALUE;
  if (x > maxv) maxv = x;
  if (y > maxv) maxv = y;
  if (z > maxv) maxv = z;
  return maxv;
}

课后题：求最长递增子序列长度

300. Longest Increasing Subsequence

我们有一个数字序列包含 n 个不同的数字，如何求出这个序列中的最长递增子序列长度？比如 2, 9, 3, 6, 5, 1, 7 这样一组数字序列，它的最长递增子序列就是 2, 3, 5, 7，所以最长递增子序列的长度是 4。