从最短编辑距离问题到初识动态规划

# 从最短编辑距离问题到初识动态规划

先说些题外话：

作为一个算法小白，我在领到最短编辑距离这个讲题的时候头就秃了一半，在后面看动态规划的时候剩下一半还不够我秃的👨‍🦲。

今天的题目虽然是从最短编辑距离到初识动态规划，但实际上，要解最短编辑距离，还是得从动态规划开始。

动态规划（Dynamic Programming），是一种用于求解最优问题的算法，相对其他算法（如回溯算法：穷举所有可能，时间复杂度为指数级），动态规划可以显著地降低时间复杂度。但是动态规划并不好学，而且因为某种莫名的力量，是众所周知的难学。主要是因为动态规划“求解问题的过程不太符合人类常规的思维方式”。

动态规划将问题分为多个决策阶段，每个阶段做一个决策（选择），记录每个阶段做完决策的状态，通过上一个阶段的状态推导出下一个阶段的状态，动态地推演。(划重点)

# 0-1背包问题

学习动态规划，主要还是多练，~~所以这是一节习题课......~~下面我们先通过一个非常著名的0-1背包问题，认识一下动态规划。

问：

有一个承重为w的背包，可装载的物品共有n个，在重量分别为weight（一个代表不同物品重量的数组）的物品中，可装载的重量最大值是多少？

如：背包可装9kg，5个物品，提供的物品有[2,2,4,6,3]kg

解：

我们将问题分解为物品总个数个阶段，每个阶段决策当前物品是否装入背包，每个阶段状态即当前总重量是否可达。即，挨个选择要不要这个物品。这个过程可以画一张表格来表示，1表示状态可达，0表示状态不可达。

	0	2	3	4	5	6	7	8	9
w=2	1	1	0	0	0	0	0	0	0
w=2	1	1	0	1	0	0	0	0	0
w=4	1	1	0	1	0	1	0	1	0
w=6	1	1	0	1	0	1	0	1	0
w=3	1	1	1	1	1	1	1	1	1

这个表格我们称为状态转移表，有了状态转移表，就可以用代码来描述这个表格：

定义数组=>初始化边界值=>推演

// weight:物品重量，n:物品个数，w:背包可承载重量
function knapsack(weight = [2,2,4,6,3], n = 5, w = 9) {
  // 定义二维数组
  let state = []
  for(let i = 0; i < n; i++) {
    state[i]=[]
  }
  
  // 初始化第一行数据
  state[0][0]=true
  if(weight[0] < w){
    state[0][weight[0]] = true
  }

  // 动态规划状态转移
  for(let i = 1; i < n; i++) {
    // 决策为不放入背包
    for(let j = 0; j <= w; j++) {
      if(state[i-1][j]) state[i][j]=state[i-1][j]
    }
    // 决策为放入背包
    for(let j = 0; j <= w - weight[i]; j++) {
      if(state[i-1][j]) state[i][j+weight[i]]=true
    }
  }

  for(let i = w; i >= 0; i--) {
    if(state[n-1][i]) return i
  }

  return 0
}

结论：

这串代码的时间复杂度为O(n*w)，但是额外申请了一个n*(w+1)的数组。

所以有时候我们说动态规划是拿空间来换时间。

优化：

实际上，这段代码还可以优化成一维数组：

function knapsack2(weight = [2,2,4,6,3], n = 5, w = 9) {
  // 定义数组
  let state = []
  // 初始化
  state[0]=true
  if(weight[0] < w){
    state[weight[0]] = true
  }

  // 动态规划状态转移
  for(let i = 1; i < n; i++) {
    // 决策为放入背包
    for(let j = w-weight[i]; j >= 0; j--) { // 为了避免重复计算，这里从大到小开始遍历
      if(state[j]) state[j+weight[i]]=true
    }
  }

  for(let i = w; i >= 0; i--) {
    if(state[i]) return i
  }

  return 0
}

问题升级：

如果每个物品有不同的价值，求可装入物品的最大价值是多少？

解：

对上面的状态转移表做一下优化，将状态值是/否换成当前总价值。

	2	4	5	6	7	8	9
w=2,val=1	1	0	0	0	0	0	0
w=2,val=2	1	3	0	0	0	0	0
w=4,val=4	1	3	0	5	0	7	0
w=6,val=6	1	3	0	5	0	7	0
w=3,val=2	1	3	3	5	5	7	7

用代码来描述：

// weight:物品重量，value:物品价值，n:物品个数，w:背包可承载重量
function knapsack3(weight = [2,2,4,6,3], value = [1,2,4,6,2], n = 5, w = 9) {
  // 定义二维数组
  let state = []
  for(let i = 0; i < n; i++) {
    state[i]=[]
    for(let j = 0; j <= w; j++) {
      state[i][j]=0
    }
  }
  
  // 初始化
  if(weight[0] < w){
    state[0][weight[0]] = value[0]
  }
  
  // 动态规划状态转移
  for(let i = 1; i < n; i++) {
    // 决策为不放入背包
    for(let j = 0; j <= w; j++) {
      if(state[i-1][j] > 0) state[i][j]=state[i-1][j]
    }
    
    // 决策为放入背包
    for(let j = 0; j <= w - weight[i]; j++) {
      if(state[i-1][j] > 0) state[i][j+weight[i]] = Math.max(state[i][j+weight[i]],state[i-1][j]+value[i])
    }
  }

  // 找最大值
  let max = 0
  for(let i = 0; i <= w; i++) {
    if(state[n-1][i] > max) max = state[n-1][i]
  }

  return max
}

同样对这段代码可以做空间复杂度优化：

// weight:物品重量，value:物品价值，n:物品个数，w:背包可承载重量
function knapsack4(weight = [2,2,4,6,3], value = [1,2,4,6,2], n = 5, w = 9) {
  // 定义二维数组
  let state = []
  for(let j = 0; j <= w; j++) {
    state[j]=0
  }

  // 初始化
  if(weight[0] < w){
    state[weight[0]] = value[0]
  }
  console.log(state);
  // 动态规划状态转移
  for(let i = 1; i < n; i++) {
    // 决策为放入背包
    for(let j = w - weight[i]; j >= 0; j--) {
      if(state[j] > 0) state[j+weight[i]] = Math.max(state[j+weight[i]],state[j]+value[i])
    }
  }

  // 找最大值
  let max = 0
  for(let i = 0; i <= w; i++) {
    if(state[i] > max) max = state[i]
  }

  return max
}

# 最短编辑距离

# 什么是最短编辑距离

我们常用的搜索引擎的拼写纠错功能的实现，就涉及到最短编辑距离。

编辑距离指的就是，将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。编辑距离越大，说明两个字符串的相似程度越小；相反，编辑距离就越小，说明两个字符串的相似程度越大。(《数据结构与算法之美》)

# 莱文斯坦距离

莱文斯坦距离（Levenshtein distance）是一种常用的计算最短编辑距离的方法，仅允许增加、删除、替换这三种编辑操作在改变字符串，描述两个字符串的差异大小。

以"make"和"mark"为例：

假如从"make"=>"mar"，需要a步，那么从"make"=>"mark"需要增加一个"k"，总计a+1步；

假如从"mak"=>"mark"，需要b步，那么从"make"=>"mark"需要删除一个"e"，总计b+1步；

假如从"mak"=>"mar"，需要c步，那么从"make"=>"mark"需要替换"e"为"k"，总计c+1步；

而替换的操作又分最后一个单词是否相同两种情况，相同的情况下，总计c步；

当我们求两个单词的最短编辑距离时，就可以通过上一步操作来推演：

min(a+1,b+1,c+1)或min(a+1,b+1,c)

假设"make"的第0-i个字符与"mark"的第0-j个字符之间的最短编辑距离用d[i][j]表示，那么在上面的例子中a可以表示为d[i][j-1]，b可以表示为d[i-1][j]，c可以表示为d[i-1][j-1]，于是得到：

d[i][j]=min(d[i][j-1]+1,d[i-1][j]+1,d[i-1][j-1]+1)或d[i][j]=min(d[i][j-1]+1,d[i-1][j]+1,d[i-1][j-1])

我们称之为状态转移方程。

现在有了状态转移方程，怎么画状态转移表呢？像上面的背包问题一样，推演的过程需要初始值，在这里，我们从空字符串开始考虑。从空字符串到任何一个字符串的最短编辑距离，就是这个字符串的长度。

于是可以画出状态转移表，这样思考起来会更形象：

	''	'm'	'ma'	'mak'	'make'
''	0	1	2	3	4
'm'	1
'ma'	2
'mar'	3
'mark'	4

初始化边界值之后，逐行逐列填写。

例如第二行第二列，"m"-"m"，末尾相同，取min(d[i][j-1]+1,d[i-1][j]+1,d[i-1][j-1])，填0。

再比如，"m"-"ma"，末尾不同，取min(d[i][j-1]+1,d[i-1][j]+1,d[i-1][j-1]+1)，填1。

最终填好的状态转移表如下，从"make"到"mark"需要两步。

	''	'm'	'ma'	'mak'	'make'
''	0	1	2	3	4
'm'	1	0	1	2	3
'ma'	2	1	0	1	2
'mar'	3	2	1	1	2
'mark'	4	3	2	2	2

写出推演代码：

定义数组=>特殊情况处理=>初始化边界值=>推演

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
 var minDistance = function(word1, word2) {
    let n = word1.length,
        m = word2.length;

    // 有一个字符串为空串
    if (n * m == 0) {
        return n + m;
    }

    // DP 数组
    let D = [];

    // 边界状态初始化
    // 初始化列
    for (let i = 0; i < n + 1; i++) {  
        D[i] = [i];
    }
    // 初始化第一行
    for (let j = 1; j < m + 1; j++) {
        D[0].push(j);
    }

    // 计算所有 DP 值
    for (let i = 1; i < n + 1; i++) {
        for (let j = 1; j < m + 1; j++) {
            let a = D[i - 1][j] + 1,
                b = D[i][j - 1] + 1,
                c = D[i - 1][j - 1];
            if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                c += 1;
            }
            D[i][j] = Math.min(a, b, c);
        }
    }
    return D[n][m];
};

# 最长公共子串

最长公共子串（Longest common substring length）描述的并不是最短编辑距离，而是两个字符串的相似程度，仅允许增加或删除两种操作。虽然不是用于计算最短编辑距离，但也是实现拼写纠错的一种思路。

假设有两个字符串a="dinanec"、b="dynamic"，就像背包问题一样，维护一个state二维数组在存储当前最长公共子串：

当a[i]和b[j]相同时，最长公共子串为state[i-1][j-1]+1、state[i-1][j]、state[i][j-1]中的最大值；

当a[i]和b[j]不同时，最长公共子串为state[i-1][j-1]、state[i-1][j]、state[i][j-1]中的最大值；

同样先思考边界值问题，如果其中一个字符串只有一个字符，那么它在另一个字符串中出现之前，最长公共子串为0，出现之后，最长公共子串为1。

再画一个状态转移表可能更形象：

	'd'	'dy'	'dyn'	'dyna'	'dynam'	'dynami'	'dynamic'
'd'	1	1	1	1	1	1	1
'di'	1	1
'din'	1
'dina'	1
'dinan'	1
'dinane'	1
'dinanec'	1

初始化边界值，然后逐行逐列填写。

例如，第二行第二列，"di"-"dy"，末尾不同，取max(state[i-1][j-1],state[i-1][j],state[i][j-1])，填1。

第四行第四列，"dina"-"dyna"，末尾相同，取max(state[i-1][j-1]+1,state[i-1][j],state[i][j-1])，填3。

	'd'	'dy'	'dyn'	'dyna'	'dynam'	'dynami'	'dynamic'
'd'	1	1	1	1	1	1	1
'di'	1	1	1	1	1	2	2
'din'	1	1	2	2	2	2	2
'dina'	1	1	2	3	3	3	3
'dinan'	1	1	2	3	3	3	3
'dinane'	1	1	2	3	3	3	3
'dinanec'	1	1	2	3	3	3	4

翻译成代码：

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    let l1 = text1.length, l2 = text2.length;
    
    if(l1*l2===0) return 0

    let state = [], a = text1.charAt(0), b = text2.charAt(0);

    // 初始化第一行
    state[0]=[]
    for(let i = 0; i < l2; i++){
        state[0][i] = a === text2.charAt(i)
            ? 1
            : i===0
                ? 0
                : state[0][i-1]
    }

    // 初始化第一列
    for(let i = 1; i < l1; i++){
        state[i]=[]
        state[i][0] = b === text1.charAt(i)
            ? 1
            : i===0
                ? 0
                : state[i-1][0]
    }

    // 行行推进
    for(let i = 1; i < l1; i++){
        for(let j = 1; j < l2; j++){
            state[i][j] = text1.charAt(i) === text2.charAt(j)
                            ? Math.max(state[i-1][j-1]+1,state[i-1][j],state[i][j-1])
                            : Math.max(state[i-1][j-1],state[i-1][j],state[i][j-1])
        }
    }

    return state[l1-1][l2-1]
};

# 实际场景

将用户输入与词库中的单词进行一一比较，取编辑距离最短的单词，或相似度最高的单词，提示给用户，这是拼写纠错的基本原理。但真正的搜索引擎肯定不止这么简单，一来词库数据量很大，二来要支持海量搜索，性能要求就会比较高，所以一般有所取舍。比如取出编辑距离最小的top10，根据热门搜索程度来决定，比如用多种算法，如上面这两种，然后取交集，再做取舍，再比如通过当前用户特有的搜索习惯作为优先词库，等等。

# 其他经典动态规划问题

# 变异杨辉三角问题

在杨辉三角中，某一个节点的值来自于上一层相邻两个节点的和。将它改造一下，假如每一层都可以随意填写数字，代表经过这个节点的路径长度，求到达底层的最短路径。

# 零钱兑换

有一个整数数组coins，表示不同面额的硬币，每种硬币个数无限，再指定一个总金额amount，表示总金额。求可凑成总金额所需的最少的硬币个数。

# 最长递增子序列

有一个整数数组nums，求最长递增子序列长度。

# 参考

《数据结构与算法之美》王争

← web 安全如何在element-ui中拓展一个新的组件 →

	0	2	3	4	5	6	7	8	9
w=2	1	1	0	0	0	0	0	0	0
w=2	1	1	0	1	0	0	0	0	0
w=4	1	1	0	1	0	1	0	1	0
w=6	1	1	0	1	0	1	0	1	0
w=3	1	1	1	1	1	1	1	1	1

	0	2	3	4	5	6	7	8	9
w=2	1	1	0	0	0	0	0	0	0
w=2	1	1	0	1	0	0	0	0	0
w=4	1	1	0	1	0	1	0	1	0
w=6	1	1	0	1	0	1	0	1	0
w=3	1	1	1	1	1	1	1	1	1

	0	2	3	4	5	6	7	8	9
w=2	1	1	0	0	0	0	0	0	0
w=2	1	1	0	1	0	0	0	0	0
w=4	1	1	0	1	0	1	0	1	0
w=6	1	1	0	1	0	1	0	1	0
w=3	1	1	1	1	1	1	1	1	1