动态规划，应该是在常用的算法思想中最难的一个了。它之所以难，主要有两点：一是不知道怎样的问题可以使用动态规划解决，二是不知道一个问题怎样具体地使用动态规划分析。
其实，这两者都有一定的套路可寻，下面我就为你详细分析这两个问题，并且会告诉你为什么动态规划的效率比回溯算法高：
什么样的问题可以使用动态规划解决
首先，需要明确一件事，一个算法只能在满足条件的情况下才能使用，如果条件不符，则无法使用。
对于动态规划来说，它能解决的问题主要要满足四个特点，我们称之为：一个模型，三个特征。一个模型，是指这个问题符合多阶段最优解模型，三个特点是指，这个问题具有无后向性、重复子问题和最优子结构。
下面，我们会用一个很经典的算法题目，来为你展示这四个特点。
题目是这样的：
假设我们有一个 n 乘以 n 的矩阵 w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角，终止位置在右下角。我们将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角，会有很多不同的路径可以走。我们把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢？
多阶段最优解模型
这个特点是说，一个问题可以分成多个阶段进行决策，不同的决策可能都可以解决问题，但是只有特定的某一个（或几个）解是最优的解决方案
以这个题目为例，你会发现，在一个 n * n 的矩阵中，一共要移动 2(n - 1) 次，也就是说，我们需要移动 6 次才能到达终点，这里的 6 次，就是多阶段决策。在这 6 次移动中，你都可以选择向右或者向下移动，而只有某一个移动线路可以让路径最短。
无后向性
无后向性有两个含义：
- 第一个含义是，在推导下一个阶段的状态的时候，我们只关心前面有限个状态的值，而不必追究前面这个状态是如何得到的。
- 第二个含义是，一个阶段的状态一旦确定，就不再受之后阶段决策的影响。
无后向性是一个非常宽松的条件，基本上满足多阶段最优解模型的问题，都会满足无后向性。对于这个特性，你要记住的是，不要尝试用你的大脑记住所有的决策阶段。你只要分析有限的阶段即可。
重复子问题
这个特性是指，使用不同的决策序列，可能会达到同一个状态。
以上面的例子来说，就是我们到达某一点会有不同的路径可供选择：
最优子结构
最优子结构是说，一个问题的最优解包含子问题的最优解。从两个方面来说，一是我们可以从子问题的最优解，推出问题的最优解。二是我们可以由最终问题倒推子问题。
可以说，正是因为具有这四个特征，才构成了我们使用动态规划的条件，也是因为这几个特征，才让动态规划会有比回溯算法更高的效率。那么在讲具体的解题思路之前，我们有必要了解一下为什么动态规划会如此高效。
动态规划为什么高效
聊到动态规划，我们常常拿回溯算法和它做比较。所以要理解动态规划的高效，我们首先要理解回溯算法为什么低效，动态规划是如何借助上面四个特点提高效率的。
回溯算法：暴力遍历
回溯算法是一个比动态规划更加通用的算法思想，它通过不断地尝试和回溯来获得问题的解。通常，回溯算法会穷尽问题的所有解，并进一步获得问题的最优解。依然以上面的问题为例，让我们看一下回溯算法的执行过程：
下面使用一个 3 x 3 的矩阵为例，展示了在回溯算法中探索出的两个解：
而对于这个问题来说，一共有 6 种执行路径，他们的递归树如下：
在回溯算法中，计算机会遍历所有可能的解，这也是为什么我们说回溯算法是一种暴力算法。实际上，回溯算法的时间复杂度为 O(2n)，这个复杂度是难以接受的，你可以感受一下 4 x 4 的递归过程：
那么，面对同样的问题，动态规划是如何解决的呢？
动态规划：高效剪枝和递推
剪枝和递推是我们在编程中会经常使用到的方法，一个最常见的例子就是求解斐波那契数列，使用剪枝和递推，可以让程序的复杂度飞速下降。
还记得我们之前说过的，使用动态规划的必备条件吗？在动态规划中剪枝的依据来源于重复子问题，递推的依据来源于最优子结构。接下来，我们就来看一下它们是如何发挥作用的。
剪枝和重复子问题
相信你已经察觉到了，回溯算法的递归树做了非常多的冗余操作，例如下面的这个例子：
在这个图片中，是计算机走到 (1,1) 的两个路径，你会发现，同样是走到这个这个位置，却付出了不同的代价：4 和 5，依据我们要求最短路径的需求，我们可以很自然地将代价大的一个树枝“剪掉”：
你会发现，这种优化的效果是立竿见影的。
最优子结构和递推
写出递推公式是动态规划中最重要的步骤，我们可以通过分析一个问题的最优子结构得出其递推公式。
以本题为例，棋子只能向下和向右，所以反过来想，如果一个棋子的上方和左边的状态已经确定，我们可以很自然地得到这个棋子的状态。
例如，当前棋子的位置为 ( i , j )，那么这个位置的状态只能从 ( i - 1 , j ) 和 ( i , j - 1 ) 两个状态中得出。
将这个规律总结成递推公式，就是：
min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))
接下来的事情就非常简单了，我们可以根据这个公式依次求得棋子在每一个位置的最优状态：
有了上面的讲解，你已经了解了动态规划的所有知识。本题在LeetCode上可以找到，你可以点击这里。
对这个题目的代码，有三种解法：
- 回溯（复杂度过高，无法通过提交）：
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
self.grid = grid
self.m = len(grid)
self.n = len(grid[0])
self.res = 10000
self.dg(0, 0, 0) # 从出发点开始尝试遍历
return self.res
def dg(self, i, j, s):
if i == self.m - 1 and j == self.n - 1: # 如果到达了终点，则将结果尝试保存
if self.res > s + self.grid[i][j]:
self.res = s + self.grid[i][j]
if i < self.m and j < self.n:
self.dg( i + 1, j, s + self.grid[i][j])
self.dg( i, j + 1, s + self.grid[i][j])
- 动态规划（正推）：
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
matrix = [ [ None for j in i ] for i in grid ] # 状态数组
temp = 0
for i, _i in enumerate(grid): # 初始化 y 轴
temp += grid[i][0]
matrix[i][0] = temp
temp = 0
for j, _j in enumerate(grid[0]): # 初始化 x 轴
temp += grid[0][j]
matrix[0][j] = temp
for i, _i in enumerate(grid): # 使用递推公式求状态数组
for j, _j in enumerate(_i):
if i == 0 or j == 0 :
continue
# 递推公式
matrix[i][j] = min(matrix[i - 1][j], matrix[i][j-1]) + grid[i][j]
return matrix[-1][-1]
- 递归（倒推）：
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
self.grid = grid
self.mat = [ [None for j in i] for i in grid ] # 使用一个数组暂存结果
m = len(grid)
n = len(grid[0])
return self.dg(m - 1, n - 1) # 获得终点的值
def dg(self, i, j): # 会返回 i,j 的最小值
if i == 0 and j == 0: # 递归终点：到达 0,0 点
return self.grid[i][j]
if self.mat[i][j] is not None: # 如果这个结果已经有了，就直接返回
return self.mat[i][j]
up_min = 10000
left_min = 10000
if j > 0 :
up_min = self.dg(i, j - 1)
if i > 0 :
left_min = self.dg(i - 1, j)
cur_min = min(up_min, left_min) + self.grid[i][j] # 递推公式
self.mat[i][j] = cur_min # 暂存
return cur_min
例题分析
例题1：按摩师
这道题来自LeetCode：
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
示例：
输入： [1,2,3,1]
输出： 4
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。
题目分析：
多阶段最优解模型：在示例中，一共要处理 4 次预约，不同的处理方式会有不同的结果，而我们要找的是最优解。
重复子问题：在不同的情况下，会出现不同的子问题。例如：对于第三天的按摩，我选择去或者不去，会根据之前第一天和第二天的选择有所不同，这就有重复的子问题了。
最优子结构：在不同的情况下，不同的子问题会有最优解。例如：对于第三天的按摩，不同的选择策略会有不同的按摩分钟数，其中会有最优决策。
递推公式：我们在这里需要根据题目要求给出不同的递推公式：
在这个问题中，我们需要设置状态数组 status[ i ][ j ] ，其中 i 表示按摩师对第 i 天进行决策，j 表示是否接受预约（ 0 表示不接受，1 表示接受）。
根据题目，我们可以得到递推公式：
status[ i ][ 0 ] = max( status[ i-1][ 0 ], status[ i-1 ][ 1 ] )
status[ i ][ 1 ] = status[ i-1 ][ 0 ] + nums[ i ]
OK，这样我们就可以写出代码了：
class Solution:
def massage(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
sta = [ [None, None] for i in nums ]
sta[0][0] = 0
sta[0][1] = nums[0]
i = 1
while i < len(nums):
sta[i][0] = max(sta[i - 1][0], sta[i - 1][1])
sta[i][1] = sta[i - 1][0] + nums[i]
i += 1
return max(sta[-1])
例题2：编辑距离
这道题来自LeetCode 第 72 题：
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。（即编辑距离）
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
这个题目比较有实际的应用价值，最常见的应用就是拼写纠错：
在这些例子中，系统会自动识别输入的内容，并且会将这些内容和一些常用的字符串进行匹配，如果两个字符串的编辑距离比较小，则系统判断你可能是手误打错了内容，从而进一步进行正确的推荐。
分析
在这个题目中，允许三种编辑操作：插入、删除 和 替换。
对于这三种情况，让我们看一在实际的匹配中是如何处理的：
假设我们匹配两个字符串 a 和 b ，现在在 a 字符串中匹配到第 i 个字符，b 中匹配到第 j 个字符。
- 如果 a[ i ] == b[ j ]，我们则可以进入下一次匹配：a[i + 1] 和 b[j + 1]
- 如果 a[ i ] != b[ j ]，我们则需要进行一次编辑操作：插入、删除 或者替换（注意，进行下面的操作会导致编辑距离 +1）：
- 可以删除 a[i]，然后考察 a[i+1]和 b[j]；
- 可以删除 b[j]，然后考察 a[i]和 b[j+1]；
- 可以在 a[i]前面添加一个跟 b[j]相同的字符，然后考察 a[i]和 b[j+1];
- 可以在 b[j]前面添加一个跟 a[i]相同的字符，然后考察 a[i+1]和 b[j]；
- 可以将 a[i]替换成 b[j]，或者将 b[j]替换成 a[i]，然后考察 a[i+1]和 b[j+1]。
你可以通过下面的图大致了解一下它的执行过程：
走到这里，你应该可以发现：
- 这个问题是一个多阶段最优解模型
- 这个问题中存在重复子问题
- 在重复的子问题中，存在最优解
没错，有了这些发现，你应该可以想到使用动态规划来解决这个问题。对于动态规划来说，最重要的是递推公式。
通过对题目的分析，我们已经知道，递推需要区分两种情况：a[ i ] == b[ j ] 和 a[ i ] != b[ j ]，它们的递推公式如下：
如果：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)就等于：
min(min_edist(i-1,j)+1, min_edist(i,j-1)+1，min_edist(i-1,j-1))
其中，min表示求三数中的最小值。
有了递推公式，我们就可以很容易地填充状态数组了：
它的代码如下：
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..0]与b[0..j]的编辑距离
if (a[0] == b[j]) minDist[0][j] = j;
else if (j != 0) minDist[0][j] = minDist[0][j-1]+1;
else minDist[0][j] = 1;
}
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;
}
上面的代码是专栏作者的代码，下面是我自己的代码。注意，我的代码为了方便初始化，在矩阵中多使用了一行和一列：
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
dp = [ [ None for j in range(len(word2) + 1) ] for i in range(len(word1) + 1) ] # 多使用一行和一列
# 初始化数组
for i, v in enumerate(dp[0]):
dp[0][i] = i
for i, v in enumerate(dp):
dp[i][0] = i
i = 1
while i <= len(word1):
j = 1
while j <= len(word2):
if word1[i - 1] == word2[j - 1]: # 递推
dp[i][j] = min(dp[i - 1][j - 1], dp[ i ][j - 1] + 1, dp[i - 1][ j ] + 1)
if word1[i - 1] != word2[j - 1]: # 递推
dp[i][j] = min(dp[i - 1][j - 1], dp[ i ][j - 1], dp[i - 1][j]) + 1
j += 1
i += 1
return dp[-1][-1]
示例：
- 输入："horse" "ros"
- 输出：3
- 状态数组：
[0, 1, 2, 3]
[1, 1, 2, 3]
[2, 2, 1, 2]
[3, 2, 2, 2]
[4, 3, 3, 2]
[5, 4, 4, 3]
如果不理解添加一行一列的原因，你可以看一下官方题解。
