动态规划的算法题往往都是各大公司笔试题的常客。在不少算法类的微信公众号中，关于“动态规划”的文章屡见不鲜，都在试图用最浅显易懂的文字来描述讲解动态规划，甚至有的用漫画来解释，认真读每一篇公众号推送的文章实际上都能读得懂，都能对动态规划有一个大概了解。
什么是动态规划？通俗地理解来说，一个问题的解决办法一看就知道（穷举），但不能一个一个数啊，你得找到最优的解决办法，换句话说题目中就会出现类似“最多”、“最少”，“一共有多少种”等提法，这些题理论上都能使用动态规划的思想来求解。动态规划与分治方法类似，都是通过组合子问题的解来求解原问题，但它对每个子问题只求解一次，将其保存在表格中，无需重新计算，通常用于求解最优化问题——《算法导论》。
编辑距离（Edit Distance），在本文指的是Levenshtein距离，也就是字符串S1通过插入、修改、删除三种操作最少能变换成字符串S2的次数。例如：S1 = abc，S2 = abf，编辑距离d = 1（只需将c修改为f）。在本文中将利用动态规划的算法思想对字符串的编辑距离求解。
定义：S1、S2表示两个字符串，S1(i)表示S1的第一个字符，d[i, j]表示S1的第i个前缀到S2的第j个前缀（例如:S1 = ”abc”,S2 = ”def”,求解S1到S2的编辑距离为d[3, 3]）。
若S1 = ”abc”, S2 = ”dec”，此时它们的编辑距离为d[3, 3] = 2，观察两个字符串的最后一个字符是相同的，也就是说S1(3) = S2(3)不需要做任何变换，故S1 = ”abc”, S2 = ”dec” <= > S1’ = ”ab”, S2’ = ”de”，即当S1[i] = S[j]时，d[i, j] = d[i-1,j -1]。得到公式：d[i, j] = d[i - 1, j - 1] (S1[i] = S2[j])
上面一条得出了当S1[i] = S2[j]的计算公式，显然还有另一种情况就是S1[i] ≠ S2[j]，若S1 = ”abc”, S2 = ”def”。S1变换到S2的过程可以“修改”，但还可以通过“插入”、“删除”使得S1变换为S2。
1)在S1字符串末位插入字符“f”，此时S1 = ”abcf”，S2 = ”def”,此时即S1[i] = S2[j]的情况，S1变换为S2的编辑距离为d[4, 3] = d[3, 2]。所以得出d[i, j]=d[i, j - 1] + 1。（+1是因为S1新增了”f”）
2)在S2字符串末位插入字符“c”，此时S1 = ”abc”，S2 = ”defc”，此时即S1[i] = S[j]的情况，S1变换为S2的编辑距离为d[3, 4] = d[2, 3]。所以得出d[i, j]=d[i - 1, j] + 1，实际上这是对S1做了删除。（+1是因为S2新增了”c”）
3)将S1字符串末位字符修改为”f”，此时S1 = ”abf”，S2 = ”def”，此时即S1[i] = S[j]的情况，S1变换为S2的编辑距离为d[3, 3] = d[2, 2]。所以得出d[i, j] = d[i – 1, j - 1] + 1。（+1是因为S1修改了“c”）
综上，得出递推公式：
=>
不妨用表格表示出动态规划对S1=”abc”，S2=“def”的求解过程。
可以看出红色方块即是最终所求的编辑距离，整个求解过程就是填满这个表——二维数组。下面是Java、Python分别对字符串编辑距离的动态规划求解。
Java
1 package com.algorithm.dynamicprogramming; 2 3
/** 4 * 动态规划——字符串的编辑距离 5 * s1 = "abc", s2 = "def" 6
* 计算公式： 7 * | 0
i = 0, j = 0 8 * | j
i = 0, j > 0 9 * d[i,j] = | i
i > 0, j = 0 10 * | min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1]) s1(i) = s2(j) 11
* | min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1]+1) s1(i) ≠ s2(j) 12 * 定义二维数组[4][4]： 13
* d e f d e f 14 * |x|x|x|x| |0|1|2|3| 15
* a |x|x|x|x| => a |1|1|2|3| => 编辑距离d = [3][3] = 3 16 * b |x|x|x|x|
b |2|2|2|3| 17 * c |x|x|x|x| c |3|3|3|3| 18 * 19 * Created by yulinfeng on 6/29/17. 20
*/ 21 public class Levenshtein { 22 23 public static void main(String[] args) { 24
String s1 = "abc"; 25 String s2 = "def"; 26 int editDistance = levenshtein(s1, s2); 27
System.out.println("s1=" + s1 + "与s2=" + s2 + "的编辑距离为：" + editDistance); 28 } 29 30 /** 31
* 编辑距离求解 32 * @param s1 字符串s1 33 * @param s2 字符串s2 34 * @return 编辑距离 35
*/ 36 private static int levenshtein(String s1, String s2) { 37 int i = 0; //s1字符串中的字符下标 38
int j = 0; //s2字符串中的字符下标 39 char s1i = 0; //s1字符串第i个字符 40
char s2j = 0; //s2字符串第j个字符 41 int m = s1.length(); //s1字符串长度 42
int n = s2.length(); //s2字符串长度 43 if (m == 0) {
//s1字符串长度为0，此时的编辑距离就是s2字符串长度 44 return n; 45 } 46
if (n == 0) { 47 return m; //s2字符串长度为0，此时的编辑距离就是s1字符串长度 48 }
int[][] solutionMatrix = new int[m + 1][n + 1]; //求解矩阵 50
/** 51 *
d e f 52 * |0|x|x|x| 53
* a |1|x|x|x| 54
* b |2|x|x|x| 55
* c |3|x|x|x| 56 */ 57 for (i = 0; i < m + 1; i++) { 58 solutionMatrix[i][0] = i; 59 } 60
/** 61 * d e f 62
* |0|1|2|3| 63
* a |x|x|x|x| 64
* b |x|x|x|x| 65
* c |x|x|x|x| 66 */ 67 for (j = 0; j < n + 1; j++) { 68 solutionMatrix[0][j] = j; 69 } 70
/** 71 * 上面两个操作后，求解矩阵变为 72
* d e f 73
* |0|1|2|3| 74
* a |1|x|x|x| 75
* b |2|x|x|x| 76
* c |3|x|x|x| 77
* 接下来就是填充剩余表格 78
*/ 79 for (i = 1; i < m + 1; i++) { //i = 1,j = 1, 2, 3，以行开始填充 80 s1i = s1.charAt(i - 1); 81
for (j = 1; j < n + 1; j++) { 82 s2j = s2.charAt(j - 1); 83 int flag = (s1i == s2j) ? 0 : 1;
//根据公式，如果s1[i] = s2[j]，则d[i,j]=d[i-1,j-1]，如果s1[i] ≠ s2[j]，则其中一个公式为d[i,j]=d[i-1,j-1]+1 84
solutionMatrix[i][j] = min(solutionMatrix[i][j-1] + 1, solutionMatrix[i-1][j] + 1, solutionMatrix[i-1][j-1] + flag); 85
} 86 } 87 return solutionMatrix[m][n]; 88 } 89 90 /** 91 * 根据公式求解编辑距离 92
* @param insert s1插入操作 93 * @param delete s1删除操作 94 * @param edit s1修改操作 95 * @return 编辑距离 96
*/ 97 private static int min(int insert, int delete, int edit) { 98 int tmp = insert < delete ? insert : delete; 99
return tmp < edit ? tmp : edit;100 }101 }Python3
1 ''' 2 动态规划——字符串的编辑距离 3 s1 = "abc", s2 = "def" 4 计算公式： 5 | 0 i = 0, j = 0 6 | j i = 0, j > 0 7 d[i,j] = | i i > 0, j = 0 8 | min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1]) s1(i) = s2(j) 9 | min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1]+1) s1(i) ≠ s2(j)10 定义二维数组[4][4]：11 d e f d e f12 |x|x|x|x| |0|1|2|3|13 a |x|x|x|x| => a |1|1|2|3| => 编辑距离d = [4][4] = 314 b |x|x|x|x| b |2|2|2|3|15 c |x|x|x|x| c |3|3|3|3|16 '''17 def levenshtein(s1, s2):18 i = 0 #s1字符串中的字符下标19 j = 0 #s2字符串中的字符下标20 s1i = "" #s1字符串第i个字符21 s2j = "" #s2字符串第j个字符22 m = len(s1) #s1字符串长度23 n = len(s2) #s2字符串长度24 if m == 0:25 return n #s1字符串长度为0，此时的编辑距离就是s2字符串长度26 if n == 0:27 return m #s2字符串长度为0，此时的编辑距离就是s1字符串长度28 solutionMatrix = [[0 for col in range(n + 1)] for row in range(m + 1)] #长为m+1，宽为n+1的矩阵29 '''30 d e f31 |0|x|x|x|32 a |1|x|x|x|33 b |2|x|x|x|34 c |3|x|x|x|35 '''36 for i in range(m + 1):37 solutionMatrix[i][0] = i38 '''39 d e f40 |0|1|2|3|41 a |x|x|x|x|42 b |x|x|x|x|43 c |x|x|x|x|44 45 '''46 for j in range(n + 1):47 solutionMatrix[0][j] = j48 '''49 上面两个操作后，求解矩阵变为50 d e f51 |0|1|2|3|52 a |1|x|x|x|53 b |2|x|x|x|54 c |3|x|x|x|55 接下来就是填充剩余表格56 '''57 for x in range(1, m + 1):58 s1i = s1[x - 1]59 for y in range(1, n + 1):60 s2j = s2[y - 1]61 flag = 0 if s1i == s2j else 162 solutionMatrix[x][y] = min(solutionMatrix[x][y-1] + 1, solutionMatrix[x-1][y] + 1, solutionMatrix[x-1][y-1] + flag)63 64 return solutionMatrix[m][n]65 66 def min(insert, delete, edit):67 tmp = insert if insert < delete else delete68 return tmp if tmp < edit else edit69 70 s1 = "abc"71 s2 = "def"72 distance = levenshtein(s1, s2)73 print(distance)
Atas ialah kandungan terperinci 字符串的编辑距离实例详解. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
js rentetan kepada tatasusunan
js untuk memintas rentetan
Ringkasan pengetahuan asas java
Pengenalan kepada rentetan
Bagaimana untuk membaca fail dan menukarnya menjadi rentetan dalam java
Bagaimana untuk menentukan rentetan dalam php
Bagaimana untuk mendapatkan panjang tatasusunan dalam js
Perbezaan antara mac air dan pro
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
