《数据结构与算法之美》基础篇笔记（六）

摘要：极客时间《数据结构与算法之美》基础篇笔记，算法思想：贪心算法、分治算法、回溯算法、动态规划

算法思想

贪心算法（greedy algorithm）

贪心算法解决问题的步骤：
1、联想到贪心算法：针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大；
2、尝试看下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据；
3、举几个例子看下贪心算法产生的结果是否是最优的
但如果前面的选择，会影响后面的选择，则不适合使用贪心算法

常见实例

1、分糖果
有 m 个大小不一的糖果和 n 个孩子，但m<n。此外，只有糖果的大小大于等于孩子的对糖果大小的需求时，孩子才会满足。如何分配糖果才能满足最多数量的孩子？
分析：糖果数量少于孩子数量，让满足的孩子的数量（期望值）最多，限制值是糖果的个数
每次从剩下的孩子中，找出对糖果大小需求最小的，然后发给他剩下的糖果中能满足他的最小的糖果
2、钱币找零
有多张不同价值的纸币，要用这些钱来支付 K 元，最少要用多少张纸币？
分析：在贡献相同期望值（纸币数目）的情况下，希望每张纸币多贡献点金额，这样就可以让纸币数更少
先用面值最大的纸币来支付，如果不够就使用更小一点的面值，以此类推，最后使用 1 元补齐
3、区间覆盖
假设有 n 个区间，从这 n 个区间中选出一部分区间，这部分区间满足两两不相交（端点相交的情况不算相交），最多能选出多少个区间？
分析：假设这 n 个区间中最左端点是 lmin，最右端点是 rmax。这个问题就相当于，选择几个不相交的区间，从左到右将 [lmin, rmax] 覆盖上
按照起始端点从小到大的顺序对这 n 个区间排序，每次选择左端点跟前面已经覆盖的区间不重合的，右端点又尽量小的区间，这样可以让剩下的未覆盖区间尽可能的大，就可以放置更多的区间

霍夫曼编码（Huffman Coding）

霍夫曼编码是利用贪心算法来实现对数据压缩编码，有效节省数据存储空间：把出现频率比较多的字符，用稍微短一些的编码；出现频率比较少的字符，用稍微长一些的编码。
具体方法：把每个字符看作一个节点，并且附带着把频率放到优先级队列中，频率小的在前面。从队列中取出频率最小的两个节点 A、B，然后新建一个节点 C，把频率设置为两个节点的频率之和，并把这个新节点 C 作为节点 A、B 的父节点。最后再把 C 节点放入到优先级队列中。重复这个过程，直到队列中没有数据，给每一条边加上画一个权值，指向左子节点的边标记为 0，指向右子节点的边，标记为 1，那从根节点到叶节点的路径就是叶节点对应字符的霍夫曼编码。
假设字符 a，b，c，d，e，f 的出现次数依次为 6，5，4，3，2，1，那么其霍夫曼编码为：
霍夫曼编码

分治算法（Divide And Conquer）

分治算法是一种处理问题的思想，递归是一种编程技巧。分治算法一般都比较适合用递归来实现
当满足以下条件时，可以使用分治算法解决问题：
1、原问题与分解成的小问题具有相同的模式；
2、原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别；
3、具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
4、可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。

应用

分治算法求出一组数据的逆序对个数：
套用分治的思想来求数组 A 的逆序对个数，将数组分成前后两半 A1 和 A2，分别计算 A1 和 A2 的逆序对个数 K1 和 K2，然后再计算 A1 与 A2 之间的逆序对个数 K3。那数组 A 的逆序对个数就等于 K1+K2+K3。这里需要借助归并排序算法来计算逆序对个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
private int num = 0; // 全局变量或者成员变量，记录逆序对个数
// a 为数组，n 为数组长度
public int count(int[] a, int n) {
  num = 0;
  mergeSortCounting(a, 0, n - 1);
  return num;
}
// 递归
private void mergeSortCounting(int[] a, int p, int r) {
  if (p >= r) return;
  int q = (p + r) / 2;
  mergeSortCounting(a, p, q);
  mergeSortCounting(a, q + 1, r);
  merge(a, p, q, r);
}
// 归并
private void merge(int[] a, int p, int q, int r) {
  int i = p, j = q + 1, k = 0; // i 是前一半数组的索引，j 是后一半数组的索引
  int[] tmp = new int[r - p + 1];
  while (i <= q && j <= r) {
    if (a[i] <= a[j]) { // 数组前面的元素不大于后面的元素，说明是有序对
      tmp[k++] = a[i++]; // 拷贝前一半数组元素后 k、i 都要 +1
    } else { // 数组前面的元素小于后面的元素，说明是逆序对
      num += (q - i + 1); // 因为在前一半数组 i-q 中，a[i] 是最小的，也就是说 i 后面的元素都比 a[j] 大，统计 i-q 之间的个数即逆序对个数
      tmp[k++] = a[j++]; // 拷贝后一半数组元素后 k、j 都要 +1
    }
  }
  while (i <= q) { // 处理前一半数组剩下的元素
    tmp[k++] = a[i++];
  }
  while (j <= r) { // 处理后一半数组剩下的元素
    tmp[k++] = a[j++];
  }
  for (i = 0; i <= r - p; ++i) { // 从 tmp 拷贝回 a
    a[p + i] = tmp[i];
  }
}

重点是归并合并两个数组的同时，计算对应的逆序度

回溯算法（Back Tracking）

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯算法非常适合用递归代码实现

八皇后问题

有一个 8x8 的棋盘，希望往里放 8 个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int[] result = new int[8]; // 下标表示行，值表示 queen 存储在哪一列
public void cal8queens(int row) { // 调用方式：cal8queens(0);
  if (row == 8) { // 8 个棋子都放置好了，打印结果
    printQueens(result);
    return; // 8行棋子都放好了，已经没法再往下递归了，所以就return
  }
  for (int column = 0; column < 8; ++column) { // 每一行都有 8 中放法
    if (isOk(row, column)) { // 有些放法不满足要求
      result[row] = column; // 第 row 行的棋子放到了 column 列
      cal8queens(row+1); // 考察下一行
    }
  }
}
// 判断 row 行 column 列放置是否合适
private boolean isOk(int row, int column) {
  int leftup = column - 1, rightup = column + 1;
  for (int i = row-1; i >= 0; --i) { // 逐行往上考察每一行
    if (result[i] == column) return false; // 第 i 行的 column 列是否有棋子
    if (leftup >= 0) { // 考察左上对角线：第 i 行 leftup 列是否有棋子
      if (result[i] == leftup) return false;
    }
    if (rightup < 8) { // 考察右上对角线：第 i 行 rightup 列是否有棋子
      if (result[i] == rightup) return false;
    }
    --leftup; ++rightup;
  }
  return true;
}
// 打印出一个二维矩阵
private void printQueens(int[] result) {
  for (int row = 0; row < 8; ++row) {
    for (int column = 0; column < 8; ++column) {
      if (result[row] == column) System.out.print("Q ");
      else System.out.print("* ");
    }
    System.out.println();
  }
  System.out.println();
}

isOk 是向上判断的，所以只有前面放置棋子符合要求才会继续放置下一个棋子。又因为外面是一个 for 循环，将每一行中的 8 列都遍历了一遍，那么一行的所有情况都会遍历到，也就不需要 result 的回退复原了。所以能够执行下去的一定是都满足需求的情况，不满足的情况都终止了。

0-1 背包问题

假设有一个背包，背包总的承载重量是 Wkg。现在有 n 个物品，每个物品的重量不等，并且不可分割。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？把物品依次排列，整个问题就分解为了 n 个阶段，每个阶段对应一个物品怎么选择。回溯法解决这个问题的时间复杂度为 O(2^n)：先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品，每次决策都有放或者不放两种方法，一共有 n 次 决策。假设背包可承受重量 100，物品个数 10，物品重量存储在数组 a 中：

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxW = Integer.MIN_VALUE; // 存储背包中物品总重量的最大值
// i 表示考察到哪个物品了；cw 表示当前已经装进去的物品的重量和；items 表示每个物品的重量；n 表示物品个数；w 背包重量
public void f(int i, int cw, int[] items, int n, int w) {
  if (cw == w || i == n) { // cw==w 表示装满了；i==n 表示已经考察完所有的物品
    if (cw > maxW) maxW = cw;
    return;
  }
  f(i+1, cw, items, n, w); // 当前物品不装进背包
  if (cw + items[i] <= w) { // 已经超过可以背包承受的重量的时候，就不要再装了
    f(i+1, cw + items[i], items, n, w); // 当前物品装进背包
  }
}
// 调用 f(0, 0, a, 10, 100) 得到 maxW

可以把输入的变量都定义成了成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private int maxW = Integer.MIN_VALUE; // 结果放到 maxW 中
private int[] weight = {2，2，4，6，3};  // 假设物品重量分别是 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个物品
  }
}

其实还可以优化，使用递归树将回溯求解过程展示出来：递归树中的每个节点 （i, cw） 表示一种状态，表示要决策到第 i 步时，背包重量为 cw 状态。
0-1背包问题
将每个状态都记录到“备忘录”中，如果之前已经计算过这种状态，那么当再次遇到的时候可以直接从备忘录中取出，避免冗余的计算。在这个问题里，如果已经有这个状态，说明经过前面的 i 次决策后，又有与之前相同状态的分支，只计算前面那次就行，后面的可以直接跳过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int maxW = Integer.MIN_VALUE; // 结果放到 maxW 中
private int[] weight = {2，2，4，6，3}; // 假设物品重量分别是 2 2 4 6 3
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
private boolean[][] mem = new boolean[5][10]; // 备忘录，默认值 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 个物品
  }
}

0-1 背包问题升级版

有一组不同重量、不同价值、不可分割的物品，将某些物品装入背包，在满足背包最大重量限制的前提下，背包中装入物品的最大价值是多少

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 个物品
  }
}

正则表达式

假设正则表达式中只包含“”和“?”这两种通配符，且与正常的正则匹配意思不一样：“”表示匹配任意多个（大于等于 0 个）任意字符，“?”表示匹配零个或者一个任意字符。用回溯算法来判断一个给定的文本能否跟给定的正则表达式匹配相匹配：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Pattern {
  private boolean matched = false; // 是否匹配标识
  private char[] pattern; // 正则表达式
  private int plen; // 正则表达式长度

  // 设置正则表达式及长度
  public Pattern(char[] pattern, int plen) {
    this.pattern = pattern;
    this.plen = plen;
  }
  
  // 文本串及长度
  public boolean match(char[] text, int tlen) {
    matched = false;
    rmatch(0, 0, text, tlen);
    return matched;
  }
  
  // 文本索引，正则表达式索引，文本串，文本长度
  private void rmatch(int ti, int pj, char[] text, int tlen) {
    if (matched) return; // 如果已经匹配，就不要继续递归
    if (pj == plen) { // 正则表达式到结尾
      if (ti == tlen) matched = true; // 文本串也到结尾
      return;
    }
    if (pattern[pj] == '*') { // * 匹配任意多个任意字符
      for (int k = 0; k <= tlen-ti; ++k) { // 枚举所有匹配 * 的情况
        rmatch(ti+k, pj+1, text, tlen);
      }
    } else if (pattern[pj] == '?') { // ? 匹配 0 个或者 1 个任意字符
      rmatch(ti, pj+1, text, tlen);  // 匹配 0，即没有匹配字符，直接跳过 ？匹配下一个字符
      rmatch(ti+1, pj+1, text, tlen); // 匹配 1，即匹配一个任意字符，然后匹配下一个字符
    } else if (ti < tlen && pattern[pj] == text[ti]) { // 纯字符匹配
      rmatch(ti+1, pj+1, text, tlen);
    }
  }
}

动态规划（Dynamic Programming）

动态规划是一个以空间换时间的算法。把问题分解为多个阶段，每个阶段对应一个决策。只记录每一个阶段可达的状态集合（去掉重复的），然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。动态规划比较适合用来求解最优问题，比如求最大值、最小值等等。

0-1 背包问题

动态规划的解决方法：把整个过程分为 n 个阶段，每个阶段决策一个物品是否放到背包中，每个物品决策完后会有很多种情况（状态），只记录不同的状态，然后对应到前面的递归树上，就是有很多不同的节点 (i, cw)。现在只记录下每层不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合。这样做可以保证每层不同状态的个数不超过 w 个（w 为背包可承载的重量），因为可能的最大值在 0-w 之间，也就是 1，2，3…w 中的某个值。而其他的都不符合要求，也就避免了每层状态个数的指数级增长。动态规划解决这个问题的时间复杂度为 O(n*w)
使用一个二维数组 states[n][w+1] 来记录每层可以达到的不同状态。像上面的 2 2 4 6 3 这组重量，从第一个物品（下标为 0）开始，不放入背包的话 states[0][0]=true，放入背包则 states[0][2]=true；决策第二个物品放不放背包中，会有三种不同状态 states[1][0]=true states[1][2]=true states[1][4]=true；依次类推，直到最后一层找到最接近 w 的值（这里是 9）就是最大的重量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// weight:物品重量，n:物品个数，w:背包可承载重量
public int knapsack(int[] weight, int n, int w) {
  boolean[][] states = new boolean[n][w+1]; // 默认值 false
  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];
    }
    for (int j = 0; j <= w-weight[i]; ++j) { // 把第 i 个物品放入背包，要求此时背包还能装下 weight[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;
}

其实可以基于一个长度为 w+1 的一维数组来操作，只需要记录每层最新的决策状态即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// weight:物品重量，n:物品个数，w:背包可承载重量
public static int knapsack2(int[] weight, int n, int w) {
  boolean[] states = new boolean[w+1]; // 默认值 false
  states[0] = true;  // 第一行的数据要特殊处理，可以利用哨兵优化
  if (weight[0] <= w) {
    states[weight[0]] = true;
  }
  for (int i = 1; i < n; ++i) { // 动态规划
    for (int j = w-weight[i]; j >= 0; --j) { // 把第 i 个物品放入背包
      if (states[j] == true) states[j+weight[i]] = true;
    }
  }
  for (int i = w; i >= 0; --i) { // 输出结果
    if (states[i] == true) return i;
  }
  return 0;
}

注意代码中 j 要从大到小遍历，因为从小到大遍历时，上一层的临时状态还未被访问就被本层前面的决策状态覆盖了，后面的状态更新时就会重复计算状态导致失真。动态规划具有无后效性，后面的状态不会影响前面的状态，从后往前计算就不会出现信息丢失

0-1 背包问题升级版

类似上面的解法：每个节点记为 f(i, cw, cv)，其中的 i 表示要决策的第 i 个物品是否放入背包，cw 表示当前背包中的物品重量，cv 表示背包中物品的总价值。合并 i 和 cw 都相同的决策，只需要保留 cv 最大的这种状态，继续递归，其他的可以忽略。用一个二维数组 states[n][w+1]，来记录每层可以达到的状态（价值）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// weight:物品重量，value:物品价值，n:物品个数，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; // 不添加第一个物品
  if (weight[0] <= w) { // 添加第一个物品
    states[0][weight[0]] = value[0];
  }
  for (int i = 1; i < n; ++i) { // 动态规划，状态转移
    for (int j = 0; j <= w; ++j) { // 不选择第 i 个物品，states[i] 与 states[i-1] 应该相等，相当于将上层数据复制到本层
      if (states[i-1][j] >= 0) states[i][j] = states[i-1][j];
    }
    for (int j = 0; j <= w-weight[i]; ++j) { // 选择第 i 个物品，还能装下 weight[i] 重量物品的状态才满足要求
      if (states[i-1][j] >= 0) { // 大于 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;
}

满减购物

活动满 200 减 30，如何才能使选出来的商品价格总和最大程度地接近 200？并且还要显示出购买哪些商品才能达到这种状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// items:商品价格，n:商品个数, w:表示满减条件，200
public static void double11advance(int[] items, int n, int w) {
  boolean[][] states = new boolean[n][3*w+1]; // 3*w+1 相当于本次购物的最大预算，超过 3 倍就没有薅羊毛的意义
  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; // 没有可行解
  for (int i = n-1; i >= 1; --i) { // i 表示二维数组中的行，j 表示列
    // 状态 (i, j) 只有可能从 (i-1, j-value[i]) 购买商品 或者 (i-1, j) 不购买商品两个状态推导过来，如果这两个状态都符合要求，选择其中一种即可，这里默认选择购买
    if(j-items[i] >= 0 && states[i-1][j-items[i]] == true) { // 购买商品
      System.out.print(items[i] + " ");
      j = j - items[i]; // 金额减少
    }
    // 没有购买这个商品，j 金额不变
  }
  if (j != 0) System.out.print(items[0]);
}

动态规划理论

使用动态规划可以解决的问题符合“一个模型三个特征”
一个模型：多阶段决策最优解模型。解决问题的过程中，需要经历多个决策阶段，每个阶段对应一组状态。然后其中一组决策序列能够产生最终期望求解的最优值。
三个特征分别是最优子结构、无后效性和重复子问题
最优子结构：问题的最优解包含子问题的最优解，也可以通过子问题的最优解，推导出问题的最优解
无后效性：1、在推到后面阶段状态时，只关注这个状态值，而不关心怎么得到这种状态的；2、某阶段状态一旦确定，就不受后面决策的影响
重复子问题：不同的决策序列，可能会产生重复的状态

动态规划解题思路

1、状态转移表法
思路：回溯算法实现 -> 定义状态 -> 画递归树 -> 找重复子问题 -> 画状态转移表 -> 根据递推关系填表 -> 将填表过程翻译成代码
一般能用动态规划解决的问题，都可以使用回溯算法的暴力搜索解决。先用简单的回溯算法解决，然后定义状态，每个状态表示一个节点，然后对应画出递归树，从递归树中查找有无重复子问题。如果找到重复的子问题，可以使用回溯加“备忘录”的方法避免重复子问题，也可以使用动态规划的状态转移表法。状态表一般都是二维的，每个状态包含三个变量，行、列、数组值。根据决策的先后过程，从前往后，分阶段填充状态表中的每个状态，最后将这个填表的过程翻译成动态规划代码。
例如：从左上角移动到右下角，使路径上的数字之和最小
动态规划-最短路径
从图中可以看出：min_dist(i, j) 可以通过 min_dist(i, j-1) 和 min_dist(i-1, j) 两个状态推导出来，即min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 回溯法
private int minDist = Integer.MAX_VALUE; // 全局变量或者成员变量
// i:：行，j:：列，dist:：数字之和，w:：二维数字表，n:：数组长度
public void minDistBT(int i, int j, int dist, int[][] w, int n) {
  // 到达了 n-1, n-1 这个位置了
  if (i == n-1 && j == n-1) {
    if (dist < minDist) minDist = dist;
    return;
  }
  if (i < n-1) { // 往下走，更新 i=i+1, j=j
    minDistBT(i + 1, j, dist+w[i][j], w, n);
  }
  if (j < n-1) { // 往右走，更新 i=i, j=j+1
    minDistBT(i, j + 1, dist+w[i][j], w, n);
  }
}
// 调用方式：minDistBacktracing(0, 0, 0, w, n)

根据回溯法画出递归树
动态规划-递归树
每个节点状态记为 (i,j,dist)，其中 i，j 分别表示行和列，dist 表示从起点到达 (i, j) 的数字之和。同时合并 i、j 相同的节点，仅保留 dist 的最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// matrix：二维数组，n：数组长度
public int minDistDP(int[][] matrix, int n) {
  int[][] states = new int[n][n]; // 存储到达 [i][j] 的最小值
  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]); // 求出到达 [i][j] 的最小值
    }
  }
  return states[n-1][n-1];
}
  1. 状态转移方程法
    思路：找最优子结构 -> 写状态转移方程 -> 将状态转移方程翻译成代码
    状态转移方程是解决动态规划的关键，它有点类似递归的解题思路。根据最优子结构，写出递归公式，也就是所谓的状态转移方程。有两种代码实现方法，一种是递归加“备忘录”，另一种是迭代递推。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    // 递归加“备忘录”
    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) { // 调用 minDist(n-1, n-1);
      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;
    }
    迭代递推与状态转移表法的代码实现是一样的，只是思路不同

杨辉三角

现在经过某个数字只能到达下面一层相邻的两个数字，假设从第一行开始向下移动，当到达最底层时，所经过的数字之和最小（总路径最短）是多少
动态规划-杨辉三角
杨辉三角的动态规划转移方程是：S[i][j] = min(S[i-1][j],S[i-1][j-1]) + a[i][j]
其中 a 表示到这个点的 value 值，S 表示到 a[i][j] 这个点的最短路径值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 状态转移表法
int[][] matrix = {{5},{7,8},{2,3,4},{4,9,6,1},{2,7,9,4,5}};
public int yanghuiTriangle1(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;
}

// 另一种方法：将三角反过来成一个漏斗，再从上向下递推，每层保留相邻两个节点路径的较小值值，直到最下层即保留的最短路径
public int yanghuiTriangle2(int[][] matrix) {
  int length = matrix.length;
  // 用于存储每一层的状态
  int[] min = new int[length + 1];
  for (int i = length - 1; i >= 0; i--) {
    int[] rawNums = matrix[i];
    int rowLength = rawNums.length;
    for (int j = 0; j < rowLength; j++) {
      min[j] = Math.min(min[j], min[j + 1]) + rawNums[j];
    }
  }
  return min[0];
}

硬币找零

假设有 3 种不同的硬币，1 元、3 元、5 元，现在需要支付 9 元，则最少需要多少个硬币

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}

编辑距离（Edit Distance）

编辑距离指的就是，将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符），可以量化两个字符串之间的相似程度：编辑距离越大，相似程度越小；编辑距离就越小，相似程度越大；两个完全相同的字符串的编辑距离是 0。
常用的两种编辑距离计算方式：
1、莱文斯坦距离：允许增加、删除、替换字符这三个编辑操作，表示两个字符串的“差异度”，越小越相似
2、最长公共子串长度：允许增加、删除字符这两个编辑操作，表示两个字符串的“相似度”，越大越相似

莱文斯坦距离（Levenshtein distance）

计算莱温斯坦距离，实际上是把一个字符串变成另一个字符串，求出需要的最少编辑次数。
使用回溯法：如果 a[i] 与 b[j] 匹配，编辑距离不变，然后递归考察 a[i+1] 和 b[j+1] 是否匹配。
如果 a[i] 和 b[j] 不匹配，有增、删、改 3 类处理方法：
1、增：在 a[i] 前面添加一个跟 b[j] 相同的字符，然后递归考察 a[i]和 b[j+1]；或在 b[j] 前面添加一个跟 a[i] 相同的字符，然后递归考察 a[i+1] 和 b[j]。即距离 +1，然后拿其中一字符串的当前字符比较另一条字符串的下一个字符
2、删：删除 a[i]，然后递归判断 a[i+1] 和 b[j]；或删除 b[i]，然后递归判断 a[i] 和 b[j+1]。与 1 效果相同，即距离 +1，然后拿其中一字符串的当前字符比较另一条字符串的下一个字符
3、改：将 a[i] 替换成 b[j]，或将 b[j] 替换成 a[i]，然后递归考察 a[i+1]和 b[j+1]。即距离 +1，同时两条字符串都跳过当前字符，直接比较下一个字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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; // 得到最小的距离
    return;
  }
  if (a[i] == b[j]) { // 两个字符匹配，递归匹配下一个字符
    lwstBT(i + 1, j + 1, edist);
  } else { // 两个字符不匹配
    lwstBT(i + 1, j, edist + 1); // 删除 a[i] 或者 b[j] 前添加一个与 a[i] 相同的字符
    lwstBT(i, j + 1, edist + 1); // 删除 b[j] 或者 a[i] 前添加一个与 b[j] 相同的字符
    lwstBT(i + 1, j + 1, edist + 1); // 将 a[i] 和 b[j] 替换为相同字符
  }
}

画出递归树，查看是否有重复的子问题。如果存在重复子问题就可以使用动态规划来解决；如果没有重复子问题，则回溯法就是最好的方法
莱文斯坦距离-递归树
在节点的 i 与 j 相同情况下，只保留 edist 最小的值，即最少的编辑次数。
由回溯法的代码可以看出状态转移过程：到达状态 (i, j)，可以由 (i-1, j)、(i, j-1)、(i-1, j-1) 这三种状态任意一个转移而来。
根据这个转移过程得到状态转移方程：

1
2
3
4
5
// 如果：a[i]!=b[j]，由 (i-1, j)、(i, j-1)、(i-1, j-1) 这三种状态转移得到
min(min_edist(i-1, j)+1, min_edist(i, j-1)+1, min_edist(i-1, j-1)+1)
// min 求三数中的最小值的方法
// 如果：a[i]==b[j]，由 (i-1, j)、(i, j-1)、(i-1, j-1) 这三种状态转移得到
min(min_edist(i-1, j)+1, min_edist(i, j-1)+1，min_edist(i-1, j-1))

使用一个二维数组 minDist 记录每个递推过程的状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// a:第一个字符串，n:第一个字符串长度，i:行序号；b:第二个字符串，m:第二个字符串长度，j:列序号
public int lwstDP(char[] a, int n, char[] b, int m) {
  int[][] minDist = new int[n][m];
  for (int j = 0; j < m; ++j) { // 初始化第 0 行：a[0] 与字符串 b[j] 的编辑距离
    if (a[0] == b[j]) minDist[0][j] = j; // 如果两个字符相等，相当于前面的都不相等，距离为 j
    else if (j != 0) minDist[0][j] = minDist[0][j-1]+1; // 如果两个字符不相等，那么可以由前一个距离 +1 的到，j!=0 防止越界
    else minDist[0][j] = 1; // a[0]!=b[0] 时 minDist[0][0] 为 1
  }
  for (int i = 0; i < n; ++i) { // 初始化第 0 列：b[0] 与字符串 a[i] 的编辑距离
    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; // a[0]!=b[0] 时 minDist[0][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;
}

最长公共子串长度（Longest common substring length）

最长公共子串长度只允许增加和删除字符两种编辑操作，它表征的是两个字符串之间的相似程度。
如果 a[i] 与 b[j] 相匹配，那么最长公共子串长度 +1。如果不匹配，最长公共子串长度不变，然后有增或删两种处理方法：
1、在 a[i] 前增加一个字符 b[j]，然后匹配 a[i] 与 b[j+1]。或者在 b[j] 前添加一个字符 a[i]，然后匹配 a[i+1] 与 b[j]；
2、删除 a[i]，然后匹配 a[i+1] 与 b[j]。或者删除 b[j]，然后匹配 a[i] 与 b[j+1]。
则 a[i] 与 b[j] 的最长公共子串长度 max_lcs(i, j) 的可以由 max_lcs(i-1,j-1)、max_lcs(i-1, j)、 max_lcs(i, j-1) 这三种状态转移而来。相同状态下，保留最大的值。

1
2
3
4
5
// 如果 a[i]==b[j]，由 max_lcs(i-1,j-1)、max_lcs(i-1, j)、 max_lcs(i, j-1) 这三种状态转移得到
max(max_lcs(i-1,j-1)+1, max_lcs(i-1, j), max_lcs(i, j-1))
// max 求三数中的最大值的方法
// 如果 a[i]!=b[j]，由 max_lcs(i-1,j-1)、max_lcs(i-1, j)、 max_lcs(i, j-1) 这三种状态转移得到
max(max_lcs(i-1,j-1), max_lcs(i-1, j), max_lcs(i, j-1))

具体代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// a:第一个字符串，n:第一个字符串长度，i:行序号；b:第二个字符串，m:第二个字符串长度，j:列序号
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] 与字符串 b[j] 的最长公共子串长度
    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] 不相同，长度为 0
  }
  for (int i = 0; i < n; ++i) { // 初始化第 0 列：j[0] 与字符串 a[i] 的最长长度
    if (a[i] == b[0]) maxlcs[i][0] = 1; // a[0] 与 b[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;
}

最长递增子序列长度

一个数字序列包含 n 个不同的数字，求出这个序列中的最长递增子序列长度。比如 2, 9, 3, 6, 5, 1, 7 这样一组数字序列，它的最长递增子序列就是 2, 3, 5, 7，所以最长递增子序列的长度是 4。思路：a[0…i] 的最长子序列为: a[i] 之前所有比它小的元素中子序列长度最大的 +1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int longestIncreaseSubArrayDP(int[] array) {
  if (array.length < 2) return array.length;
  int[] state = new int[array.length]; // 记录对应元素最长子序列长度
  state[0] = 1;
  for (int i = 1; i < state.length; i++) {
    int max = 0;
    for (int j = 0; j < i; j++) {
      if (array[j] < array[i]) {
        if (state[j] > max) max = state[j];
      }
    }
    state[i] = max + 1;
  }
  int result = 0;
  for (int i = 0; i < state.length; i++) { // 遍历找到最长子序列长度
    if (state[i] > result) result = state[i];
  }
  return result;
}

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

持续学习