一 、动态规划（Dynamic Programming）
动态规划是解决优化问题的最强大的设计技术。
分治法将问题划分为不相交的子问题，然后递归地解决子问题，然后结合其解决方案来解决原始问题。
当子问题不是独立的时，例如当它们共享相同的子问题时，将使用动态编程。在这种情况下，分治法可能会做比必要的事情更多的工作，因为它可以多次解决同一个子问题。
动态编程只解决一次每个子问题，并将结果存储在表中，以便在需要时可以重复检索它。
动态规划是一种自下而上的方法-我们解决所有可能的小问题，然后结合以获得更大问题的解决方案。
动态规划是算法设计的一种范式，其中，通过实现子问题解决方案以及出现“ 最优原理 ” 的组合来解决优化问题。
动态规划的特点：
当问题具有以下特征时，动态规划将起作用：
- Optimal Substructure--最优子结构：如果最优解决方案包含最优子解决方案，那么问题将表现出最优子结构。
- Overlapping Subproblems--子问题重叠：当递归算法将重复访问相同的子问题时，则问题将具有子问题重叠。
如果问题具有最优子结构，则可以递归定义最佳解决方案。如果一个问题有重叠的子问题，那么我们可以通过只计算每个子问题一次来改进递归实现。
如果问题没有最佳子结构，则没有基础来定义递归算法以找到最佳解决方案。如果一个问题没有重叠的子问题，那么使用动态编程将无济于事。
如果子问题的空间足够大（即输入大小为多项式），则动态编程可能比递归更有效。
动态规划的要素
基本上，三个要素是动态规划算法的特征：
- Substructure--子结构：将给定问题分解为较小的子问题。用较小问题的解决方案表示原始问题的解决方案。
- Tablestructure--表结构：解决了子问题后，将结果存储到表中的子问题中。这样做是因为子问题解决方案已被多次重用，并且我们不想一遍又一遍地重复解决相同的问题。
- Bottom-up Computation--自下而上的计算：使用表格，将较小的子问题的解决方案组合起来以解决较大的子问题，并最终得出解决问题的解决方案。
注意：自下而上是指：
- 从最小的子问题开始。
- 结合他们的解决方案，可以解决规模不断扩大的子问题。
- 直到解决原始问题为止。
动态规划的组成部分
- Stages--阶段：问题可以分为几个子问题，称为子阶段。阶段是给定问题的一小部分。例如，在最短路径问题中，它们是由图的结构定义的。
- States--状态：每个阶段都有几个与之相关的状态。最短路径问题的状态是到达的节点。
- Decision--决策：在每个阶段，可以有多个选择，应从其中做出最佳决策。在每个阶段做出的决定都应该是最佳的；这称为阶段决策。
- Optimical policy--最优政策：这是一个决定每个阶段决策的规则；如果策略是全局最优的，则称为最优策略。这被称为最佳贝尔曼原理。
- 给定当前状态，其余每个状态的最佳选择不取决于先前的状态或决策。在最短路径问题中，没有必要知道我们如何获得节点，只要获取结果就行。
- 考虑到阶段j + 1已解决，因此存在一种递归关系，该关系确定阶段j的最佳决策。
- 最后阶段必须通过调用自身解决。
动态规划算法的发展
它可以分为四个步骤：
- 表征最佳解决方案的结构。
- 递归定义最佳解决方案的值。与分治法一样，将问题递归分为两个或多个最佳部分。这有助于确定解决方案的外观。
- 从下至上计算最佳解决方案的值（从最小的子问题开始）
- 从较小的子问题的计算值构造整个问题的最佳解决方案。
动态规划的应用
- 0/1背包问题
- 数学优化问题
- 所有对最短路径问题
- 可靠性设计问题
- 最长公共子序列（LCS）
- 飞行控制和机器人控制
- 分时：它计划作业以最大化CPU使用率
二、编辑距离（Edit Distance）
概念
编辑距离的作用主要是用来比较两个字符串的相似度的
基本的定义如下所示：
编辑距离，又称Levenshtein距离（莱文斯坦距离也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数，如果它们的距离越大，说明它们越是不同。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
这个概念是由俄罗斯科学家Vladimir Levenshtein在1965年提出来的，所以也叫 Levenshtein 距离。它可以用来做DNA分析，拼字检测，抄袭识别等等。总是比较相似的，或多或少我们可以考虑编辑距离。
在概念中，我们可以看出一些重点那就是，编辑操作只有三种。插入，删除，替换这三种操作，我们有两个字符串，将其中一个字符串经过上面的这三种操作之后，得到两个完全相同的字符串付出的代价是什么就是我们要讨论和计算的。
编辑距离算法的迭代公式：
- 长度为m的字符串A，len(A) = m
- 长度为n的字符串B，len(B) = n
则A到B的编辑距离dp公式如下：
Q2: 为什么d是一个[m+1][n+1]大小的二维数组，为什么d数组要比字符串长度大一？
A2: 考虑A、B都为空字符串，我们还是需要一个[1][1]大小的数组记录其编辑距离为0。更进一步也就是说，我们假设字符串A为"AC"，则我们需要考虑['', 'A', 'AC']三种情况。
Q1: 如何理解d[i][j]的计算公式?
A1: 第(i,j)个位置的计算需要依赖于和它相邻的三个元素(i-1,j)、(i, j-1)和(i-1,j-1)，关键是哪一个对应删除，哪一个对应于插入，哪一个对应于替换？如果此时A[i]不等于B[j]，则（下面为全文最重要部分）:
对于(i-1,j-1)时，d(i-1, j-1)表示完成从A[0,i-1]到B[0,j-1]的编辑次数，即现在A[0,i-1]=B[0,j-1]，对于(i,j)，我们直接把A[i]替换成B[j]即完成编辑。因此(i-1,j-1)对应于把A[i]用B[j]替换的一次操作
对于(i-1, j)时，d(i-1, j)表示完成从A[0, i-1]到B[0, j]的编辑次数，即现在A[0,i-1]=B[0,j]，对于(i,j)，我们直接把A[i]删除即可完成编辑，因此(i-1,j)对应于把A[i]删除的一次操作
对于(i, j-1)时，d(i, j-1)表示完成从A[0, i]到B[0, j-1]的编辑次数，即现在A[0,i]=B[0,j-1]，对于(i,j)，我们直接用B[j]插入到A[i]的位置即可完成编辑，因此(i,j-1)对应于把B[j]插到A[i]的一次操作
代码示例：
# A Naive recursive Python program to fin minimum number
# operations to convert str1 to str2
def editDistance(str1, str2, m, n):
# If first string is empty, the only option is to
# insert all characters of second string into first
if m == 0:
return n
# If second string is empty, the only option is to
# remove all characters of first string
if n == 0:
return m
# If last characters of two strings are same, nothing
# much to do. Ignore last characters and get count for
# remaining strings.
if str1[m-1]== str2[n-1]:
return editDistance(str1, str2, m-1, n-1)
# If last characters are not same, consider all three
# operations on last character of first string, recursively
# compute minimum cost for all three operations and take
# minimum of three values.
return 1 + min(editDistance(str1, str2, m, n-1), # Insert
editDistance(str1, str2, m-1, n), # Remove
editDistance(str1, str2, m-1, n-1) # Replace
)
# Driver program to test the above function
str1 = "sunday"
str2 = "saturday"
print(editDistance(str1, str2, len(str1), len(str2)) )
# This code is contributed by Bhavya Jain
结果：
3
参考链接：
分治法（Divide-and-Conquer Algorithm）经典例子分析
What is Dynamic Programming
分治法（Divide-and-Conquer Algorithm）经典例子分析
编辑距离算法（Edit Distance）
Edit Distance | DP-5
