下面先讲一下动态规划的理论知识，然后后面在根据具体几个经典案例，来看看它的实际应用。了解了理论知识，看懂了几个案例，动态规划就算入门了。
文章导航
理论知识
什么样的问题适合用动态规划来解决呢？换句话说，动态规划能解决的问题有什么规律可循呢？实际上，动态规划作为一个非常成熟的算法思想，很多人对此已经做了非常全面的总结。
一个模型三个特征
首先，我们来看，什么是“一个模型”？它指的是动态规划适合解决的问题的模型。这个模型定义为“多阶段决策最优解模型”。
我们一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。
现在，我们再来看，什么是“三个特征”？它们分别是最优子结构、无后效性和重复子问题。这三个概念比较抽象，下面逐一详细解释一下。
1. 最优子结构
最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。
2. 无后效性
无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。
3. 重复子问题
不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。
状态转移方程
我们需要分析，某个问题如何通过子问题来递归求解，也就是所谓的最优子结构。根据最优子结构，写出递归公式，也就是所谓的状态转移方程。有了状态转移方程，代码实现就非常简单了。
状态转移方程是解决动态规划的关键。如果我们能写出状态转移方程，那动态规划问题基本上就解决一大半了，而翻译成代码非常简单。但是很多动态规划问题的状态本身就不好定义，状态转移方程也就更不好想到。
理论知识可以先大概了解下，后面看完经典案例再回顾一下也就了然了。
0-1 背包问题
对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？
比如说 有5个物品，物品重量分别是 [2,2,4,6,3]，背包最大重量限制是9， 那么我们算出来背包中物品总重量的最大值就是9
比如说 有5个物品，物品重量分别是 [2,2,4,6,3]，背包最大重量限制是16， 那么我们算出来背包中物品总重量的最大值就是15
暴力解法
关于这个问题，我们可以用回溯的解决方法，也就是穷举搜索所有可能的装法，然后找出满足条件的最大值。
function findMax(weightArr, bagMaxWeight) {
let maxW = 0 // 在满足背包最大重量限制的前提下，背包中物品总重量的最大值
const n = weightArr.length
function f(index, weight) { // index表示考察第几个物品，weight表示背包当前的重量
if(weight == bagMaxWeight || index == n) { // 装满了或者考察完了
if(weight > maxW) maxW = weight
return
}
f(index + 1, weight) // 不装这个物品
const newWeight = weight + weightArr[index]
if (newWeight <= bagMaxWeight) {
f(index + 1, newWeight) // 装这个物品
}
}
f(0,0)
return maxW
}
console.log(findMax([2,2,4,6,3], 9))不过，回溯算法的复杂度比较高，是指数级别的 O(2^n)。
那有没有什么规律，可以有效降低时间复杂度呢？我们一起来看看。
如果我们把这个例子的回溯求解过程，用递归树画出来，就是下面这个样子:
递归树中的每个节点表示一种状态，我们用（i, cw）来表示。其中，i 表示将要决策第几个物品是否装入背包，cw 表示当前背包中物品的总重量。比如，（2，2）表示我们将要决策第 2 个物品是否装入背包，在决策前，背包中物品的总重量是 2。
从递归树中，你应该能会发现，有些子问题的求解是重复的，比如图中 f(2, 2) 和 f(3,4) 都被重复计算了两次。
动态规划解法
我们现在来看看动态规划是怎么做的。
我们把整个求解过程分为 n 个阶段，每个阶段会决策一个物品是否放到背包中。每个物品决策（放入或者不放入背包）完之后，背包中的物品的重量会有多种情况，也就是说，会达到多种不同的状态，对应到递归树中，就是有很多不同的节点。
我们把每一层重复的状态（节点）合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合。我们可以通过合并每一层重复的状态，这样就保证每一层不同状态的个数都不会超过 w 个（w 表示背包的承载重量），也就是例子中的 9。于是，我们就成功避免了每层状态个数的指数级增长。
我们用一个二维数组 states[n][w+1]，来记录每层可以达到的不同状态。
第 0 个（下标从 0 开始编号）物品的重量是 2，要么装入背包，要么不装入背包，决策完之后，会对应背包的两种状态，背包中物品的总重量是 0 或者 2。我们用 states[0][0]=1和 states[0][2]=1来表示这两种状态。
第 1 个物品的重量也是 2，基于之前的背包状态，在这个物品决策完之后，不同的状态有 3 个，背包中物品总重量分别是 0(0+0)，2(0+2 or 2+0)，4(2+2)。我们用 states[1][0]=1，states[1][2]=1，states[1][4]=1来表示这三种状态。
以此类推，直到考察完所有的物品后，整个 states 状态数组就都计算好了。我把整个计算的过程画了出来，你可以看看。图中 0 表示 false，1 表示 true。我们只需要在最后一层，找一个值为 1 的最接近 w（这里是 9）的值，就是背包中物品总重量的最大值。
看看代码
function findMax(weightArr, bagMaxWeight) {
const n = weightArr.length
// 初始化状态矩阵
const states = new Array(n)
for(let i = 0; i < n; i++){
states[i] = new Array(bagMaxWeight + 1).fill(0)
}
// 第一个物品的数据要特殊处理，利用哨兵优化
states[0][0] = 1;
if (weightArr[0] <= bagMaxWeight) {
states[0][weightArr[0]] = 1
}
// 第二个到最后一个物品
for (let i = 1; i < n; i++){
for(let j = 0; j <= bagMaxWeight; j++) { // 不把第i个物品放入背包
if (states[i-1][j] === 1) states[i][j] = 1
}
for(let j = 0; j <= bagMaxWeight - weightArr[i]; j++) { //把第i个物品放入背包
if (states[i-1][j] === 1) states[i][j + weightArr[i]] = 1
}
}
for (let j = bagMaxWeight; j >= 0; j--) { // 输出结果
if (states[n-1][j] === 1) return j
}
return 0
}
console.log(findMax([2,2,4,6,3], 9))状态转移方程
if (states[i-1][j] === 1) {
states[i][j] = 1
if (j + weightArr[i] <= bagMaxWeight){
states[i][j + weightArr[i]] = 1
}
}我们把问题分解为多个阶段，每个阶段对应一个决策。我们记录每一个阶段可达的状态集合（去掉重复的），然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。这也是动态规划这个名字的由来，你可以自己体会一下，是不是还挺形象的？
用回溯算法解决这个问题的时间复杂度 O(2^n)，是指数级的。那动态规划解决方案的时间复杂度是多少呢？我来分析一下。
这个代码的时间复杂度非常好分析，耗时最多的部分就是代码中的两层 for 循环，所以时间复杂度是 O(n*w)。n 表示物品个数，w 表示背包可以承载的总重量。
从理论上讲，指数级的时间复杂度肯定要比 O(n*w) 高很多，但是为了让你有更加深刻的感受，我来举一个例子给你比较一下。
我们假设有 10000 个物品，重量分布在 1 到 15000 之间，背包可以承载的总重量是 30000。如果我们用回溯算法解决，用具体的数值表示出时间复杂度，就是 2^10000，这是一个相当大的一个数字。如果我们用动态规划解决，用具体的数值表示出时间复杂度，就是 10000*30000。虽然看起来也很大，但是和 2^10000 比起来，要小太多了。
尽管动态规划的执行效率比较高，但是就刚刚的代码实现来说，我们需要额外申请一个 n 乘以 w+1 的二维数组，对空间的消耗比较多。所以，有时候，我们会说，动态规划是一种空间换时间的解决思路。你可能要问了，有什么办法可以降低空间消耗吗？
实际上，我们只需要一个大小为 w+1 的一维数组就可以解决这个问题。动态规划状态转移的过程，都可以基于这个一维数组来操作。具体的代码实现我贴在这里，你可以仔细看下。
function findMax(weightArr, bagMaxWeight) {
const n = weightArr.length
const states = new Array(bagMaxWeight + 1).fill(0)
// 第一行的数据要特殊处理，利用哨兵优化
states[0] = 1;
if (weightArr[0] <= bagMaxWeight) {
states[weightArr[0]] = 1
}
for (let i = 1; i < n; i++){
// j 需要从大到小来处理。如果我们按照 j 从小到大处理的话，会出现 for 循环重复计算的问题。
for(let j = bagMaxWeight - weightArr[i]; j >= 0; j--) {
if (states[j] === 1) states[j + weightArr[i]] = 1
}
}
for (let j = bagMaxWeight; j >= 0; j--) { // 输出结果
if (states[j] === 1) return j
}
return 0
}
console.log(findMax([2,2,4,6,3], 9))所以，最终时间复杂度是 O(n*w)，空间复杂度是 O(w)。 相比于暴力回溯算法的时间复杂度O(2^n)是效率大增，增加了空间复杂度，相当于是用空间换了时间。
购物车凑满减问题
京东的“618”购物节有各种促销活动，比如“满 300 元减 50 元”。假设你女朋友的购物车中有 n 个（n>100）想买的商品，她希望从里面选几个，在凑够满减条件的前提下，让选出来的商品价格总和最大程度地接近满减条件（300 元），这样就可以极大限度地“薅羊毛”。作为程序员的你，能不能编个代码来帮她搞定呢？
对于这个问题，你当然可以利用回溯算法，穷举所有的排列组合，看大于等于 300 并且最接近300 的组合是哪一个？但是，这样效率太低了点，时间复杂度非常高，是指数级的。当 n 很大的时候，可能“双十一”已经结束了，你的代码还没有运行出结果，这显然会让你在女朋友心中的形象大大减分。
实际上，它跟第一个例子中讲的 0-1 背包问题很像，只不过是把“重量”换成了“价格”而已。购物车中有 n 个商品。我们针对每个商品都决策是否购买。每次决策之后，对应不同的状态集合。我们还是用一个二维数组 states[n][x]，来记录每次决策之后所有可达的状态。不过，这里的 x 值是多少呢？
0-1 背包问题中，我们找的是小于等于 w 的最大值，x 就是背包的最大承载重量 w+1。对于这个问题来说，我们要找的是大于等于 300（满减条件）的值中最小的，所以就不能设置为 300 加 1 了。就这个实际的问题而言，如果要购买的物品的总价格超过 300 太多，比如 900，那这个羊毛“薅”得就没有太大意义了。所以，我们可以限定 x 值为 901。
不过，这个问题不仅要求大于等于 300 的总价格中的最小的，我们还要找出这个最小总价格对应都要购买哪些商品。实际上，我们可以利用 states 数组，倒推出这个被选择的商品序列。我先把代码写出来，待会再照着代码给你解释。
function findAdvance(priceArr, minAmount) {
const n = priceArr.length
const states = new Array(n)
maxAmount = minAmount * 3
for(let i = 0; i < n; i++){
states[i] = new Array(maxAmount + 1).fill(0)
}
// 第一个物品的数据要特殊处理，可以利用哨兵优化
states[0][0] = 1;
if (priceArr[0] <= maxAmount) {
states[0][priceArr[0]] = 1
}
for (let i = 1; i < n; i++){ // 第二个到最后一个物品
for(let j = 0; j <= maxAmount; j++) { // 不购买第i个物品
if (states[i-1][j] === 1) states[i][j] = 1
}
for(let j = 0; j <= maxAmount - priceArr[i]; j++) { // 购买第i个物品
if (states[i-1][j] === 1) states[i][j + priceArr[i]] = 1
}
}
let result
for (result = minAmount; result < maxAmount+1; ++result) {
if (states[n-1][result] === 1) break // 输出结果大于等于w的最小值
}
if(result === maxAmount+1){
return // 没有可行解
}
console.log("凑单结果为", result,"元")
for (let i = n-1; i >= 1; i--) { // i表示二维数组中的行，j表示列
if(result-priceArr[i] >= 0 && states[i-1][result-priceArr[i]] === 1) {
console.log("购买商品", i, "价格", priceArr[i]) // 购买这个商品
result = result - priceArr[i];
} // else 没有购买这个商品，j不变。
}
if (result != 0) console.log("购买商品0 价格", priceArr[0])
}
findAdvance([200, 120, 140, 150, 289], 300)杨辉三角最短路径
杨辉三角”不知道你听说过吗？我们现在对它进行一些改造。每个位置的数字可以随意填写，经过某个数字只能到达下面一层相邻的两个数字。
假设你站在第一层，往下移动，我们把移动到最底层所经过的所有数字之和，定义为路径的长度。请你编程求出从最高层移动到最底层的最短路径长度。
先看下暴力解法
function findMinDist(arr) {
const n = arr.length
let minDist = Number.MAX_SAFE_INTEGER
let count = 0
function minDistFn(i, j, dist) {
count += 1
if(i === n) {
if(dist < minDist) minDist = dist
return
}
dist = dist + arr[i][j]
minDistFn(i+1,j, dist)
minDistFn(i+1,j+1, dist)
}
minDistFn(0, 0, 0)
console.log("执行次数", count)
return minDist
}
console.log(findMinDist([
[5],
[7, 8],
[2, 3, 4],
[4, 9, 6, 1],
[2, 7, 9, 4, 5]
]))再看看动态规划
状态转移方程式：
states[i][j] = Math.min(states[i - 1][j - 1], states[i - 1][j]) + arr[i][j]
// states[i][j] 表示i,j这个节点的最短路径长度
// arr[i][j] 表示i,j这个节点的数字代码如下
function findMinDist(arr) {
const n = arr.length
const states = new Array(n)
let count = 0
for (let i = 0; i < n; i++) {
states[i] = new Array(i + 1).fill(0)
count += 1
}
states[0][0] = arr[0][0];
for (let i = 1; i < n; i++) {
states[i][0] = states[i - 1][0] + arr[i][0]
count += 1
}
for (let i = 1; i < n; i++) {
for (let j = 1; j <= i; j++) {
states[i][j] = Math.min(states[i - 1][j - 1], states[i - 1][j]) + arr[i][j]
count += 1
}
}
let minDist = Number.MAX_SAFE_INTEGER
for (let i = 0; i < n; i++) {
count += 1
if (states[n - 1][i] < minDist) minDist = states[n - 1][i]
}
console.log("执行次数", count)
return minDist
}
console.log(findMinDist([
[5],
[7, 8],
[2, 3, 4],
[4, 9, 6, 1],
[2, 7, 9, 4, 5]
]))二维矩阵最短路径
假设我们有一个 n 乘以 n 的矩阵 w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角，终止位置在右下角。我们将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角，会有很多不同的路径可以走。我们把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢？
我们先看看，这个问题是否符合“一个模型”？
从 (0, 0) 走到 (n-1, n-1)，总共要走 2*(n-1) 步，也就对应着 2*(n-1) 个阶段。每个阶段都有向右走或者向下走两种决策，并且每个阶段都会对应一个状态集合。
我们把状态定义为 min_dist(i, j)，其中 i 表示行，j 表示列。min_dist 表达式的值表示从 (0, 0) 到达 (i, j) 的最短路径长度。所以，这个问题是一个多阶段决策最优解问题，符合动态规划的模型。
我们再来看，这个问题是否符合“三个特征”？
我们可以用回溯算法来解决这个问题。如果你自己写一下代码，画一下递归树，就会发现，递归树中有重复的节点。重复的节点表示，从左上角到节点对应的位置，有多种路线，这也能说明这个问题中存在重复子问题。
如果我们走到 (i, j) 这个位置，我们只能通过 (i-1, j)，(i, j-1) 这两个位置移动过来，也就是说，我们想要计算 (i, j) 位置对应的状态，只需要关心 (i-1, j)，(i, j-1) 两个位置对应的状态，并不关心棋子是通过什么样的路线到达这两个位置的。而且，我们仅仅允许往下和往右移动，不允许后退，所以，前面阶段的状态确定之后，不会被后面阶段的决策所改变，所以，这个问题符合“无后效性”这一特征。
刚刚定义状态的时候，我们把从起始位置 (0, 0) 到 (i, j) 的最小路径，记作 min_dist(i, j)。因为我们只能往右或往下移动，所以，我们只有可能从 (i, j-1) 或者 (i-1, j) 两个位置到达 (i, j)。也就是说，到达 (i, j) 的最短路径要么经过 (i, j-1)，要么经过 (i-1, j)，而且到达 (i, j) 的最短路径肯定包含到达这两个位置的最短路径之一。换句话说就是，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))解题思路
首先，我们可以用暴力回溯算法来解决这个问题。
function findMinDist(matrix) {
let minDist = Number.MAX_SAFE_INTEGER
function minDistFn(i, j, dist, matrix) {
let n = matrix.length
let newDist = dist + matrix[i][j]
if (i === n - 1 && j === n - 1) {
if (newDist < minDist) minDist = newDist;
return
}
if (i < n - 1) {
// 往下走，更新i=i+1, j=j
minDistFn(i + 1, j, newDist, matrix);
}
if (j < n - 1) { // 往右走，更新i=i, j=j+1
minDistFn(i, j + 1, newDist, matrix);
}
}
minDistFn(0,0,0, matrix)
return minDist
}
console.log(findMinDist([
[1, 3, 4, 9],
[2, 1, 3, 4],
[5, 2, 6, 7],
[6, 8, 4, 3],
]))有了回溯代码之后，接下来，我们要画出递归树，以此来寻找重复子问题。在递归树中，一个状态（也就是一个节点）包含三个变量 (i, j, dist)，其中 i，j 分别表示行和列，dist 表示从起点到达 (i, j) 的路径长度。从图中，我们看出，尽管 (i, j, dist) 不存在重复的，但是 (i, j) 重复的有很多。对于 (i, j) 重复的节点，我们只需要选择 dist 最小的节点，继续递归求解，其他节点就可以舍弃了。
既然存在重复子问题，我们就可以尝试看下，是否可以用动态规划来解决呢？
我们画出一个二维状态表，表中的行、列表示棋子所在的位置，表中的数值表示从起点到这个位置的最短路径。我们按照决策过程，通过不断状态递推演进，将状态表填好。为了方便代码实现，我们按行来进行依次填充。
弄懂了填表的过程，代码实现就简单多了。我们将上面的过程，翻译成代码，就是下面这个样子。结合着代码、图和文字描述，应该更容易理解我讲的内容。
function findMinDist(matrix) {
let n = matrix.length
let states = new Array(n)
for (let i = 0; i < n; i++) {
states[i] = new Array(n).fill(0)
}
let sum = 0;
for (let j = 0; j < n; j++) { // 初始化states的第一行数据
sum += matrix[0][j];
states[0][j] = sum;
}
sum = 0;
for (let j = 0; j < n; j++) { // 初始化states的第一列数据
sum += matrix[j][0];
states[j][0] = sum;
}
for (let i = 1; i < n; i++) {
for (let j = 1; j < n; j++) {
states[i][j] = matrix[i][j] + Math.min(states[i][j - 1], states[i - 1][j]);
}
}
return states[n - 1][n - 1];
}
console.log(findMinDist([
[1, 3, 4, 9],
[2, 1, 3, 4],
[5, 2, 6, 7],
[6, 8, 4, 3],
]))硬币找零问题
假设我们有几种不同币值的硬币 v1，v2，……，vn（单位是元），每种币值的硬币都可以有任意个。如果我们要支付 w 元，求最少需要多少个硬币。
比如，我们有 3 种不同的硬币，1 元、3 元、5 元，我们要支付 9 元，那么最少需要 3 个硬币（3 个 3 元的硬币， 或者 1 + 3 + 5）。
状态转移方程就是：
minCoin(money) = 1 + math.Min(minCoin(money-v1, minCoin(money-v2) , minCoin(money-v3), ...)这个例子里面等价于
minCoin(money) = 1 + math.Min(minCoin(money-1) , minCoin(money-3) , minCoin(money-5))代码如下：
function minCoin(coins, amount) {
let states = new Array(amount + 1).fill(Number.MAX_SAFE_INTEGER)
for (let i = 1; i <= amount; i++) {
coins.filter(coin => coin <= i).forEach(coin => {
if (i === coin) {
states[i] = 1
} else {
states[i] = Math.min(states[i], states[i - coin]) + 1
}
})
}
return states[amount]
}
console.log(minCoin([1, 3, 5], 9))递推过程：
minCoin(1) = 1 (和某个币面值一样，直接就是1）
minCoin(2) = 1 + minCoin(1) = 2
minCoin(3) = 1 (和某个币面值一样，直接就是1）
minCoin(4) = 1 + math.Min(minCoin(4 - 1), minCoin(4 - 3))
= 1 + math.Min(minCoin(3), minCoin(1))
= 2
minCoin(5) = 1 (和某个币面值一样，直接就是1）
minCoin(6) = 1 + math.Min(minCoin(6 - 1), minCoin(6 - 3), minCoin(6 - 5))
= 1 + math.Min(minCoin(5), minCoin(3), minCoin(1))
= 2
...
minCoin(9) = 1 + math.Min(minCoin(8), minCoin(6), minCoin(4))莱文斯坦距离和最长公共子串长度
搜索引擎在用户体验方面的优化还有很多，比如你可能经常会用的拼写纠错功能。当你在搜索框中，一不小心输错单词时，搜索引擎会非常智能地检测出你的拼写错误，并且用对应的正确单词来进行搜索。作为一名软件开发工程师，你是否想过，这个功能是怎么实现的呢？
计算机只认识数字，所以要解答这个问题，我们就要先来看，如何量化两个字符串之间的相似程度呢？有一个非常著名的量化方法，那就是编辑距离
编辑距离指的就是，将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。编辑距离越大，说明两个字符串的相似程度越小；相反，编辑距离就越小，说明两个字符串的相似程度越大。对于两个完全相同的字符串来说，编辑距离就是 0。
根据所包含的编辑操作种类的不同，编辑距离有多种不同的计算方式，比较著名的有莱文斯坦距离（Levenshtein distance）和最长公共子串长度（Longest common substring length）。其中，莱文斯坦距离允许增加、删除、替换字符这三个编辑操作，最长公共子串长度只允许增加、删除字符这两个编辑操作。
而且，莱文斯坦距离和最长公共子串长度，从两个截然相反的角度，分析字符串的相似程度。莱文斯坦距离的大小，表示两个字符串差异的大小；而最长公共子串的大小，表示两个字符串相似程度的大小。
关于这两个计算方法，我举个例子给你说明一下。这里面，两个字符串 mitcmu 和 mtacnu 的莱文斯坦距离是 3，最长公共子串长度是 4。
回溯解法
用最简单的回溯算法，该如何来解决。
回溯是一个递归处理的过程。如果 a[i]与 b[j]匹配，我们递归考察 a[i+1]和 b[j+1]。
如果 a[i]与 b[j]不匹配，那我们有多种处理方式可选：
- 可以删除 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]，那么：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表示求三数中的最小值。最长公共子串长度状态转移方程
// 如果：a[i]==b[j]，那么：max_lcs(i, j)就等于：
max(max_lcs(i-1,j-1)+1, max_lcs(i-1, j), max_lcs(i, j-1))；
// 如果：a[i]!=b[j]，那么：max_lcs(i, j)就等于：
max(max_lcs(i-1,j-1), max_lcs(i-1, j), max_lcs(i, j-1))；
其中max表示求三数中的最大值。最长递增子序列
有一个数字序列包含 n 个不同的数字，如何求出这个序列中的最长递增子序列长度？
比如 2, 9, 3, 6, 5, 1, 7 这样一组数字序列，它的最长递增子序列就是 2, 3, 5, 7，所以最长递增子序列的长度是 4。
状态转移方程
max_seq(i) = 1 + max( max_seq(j1), max_seq(j2), ..., max_seq(jn)) // jn < i, 并且下标i的数字要大于下标jn的数字
免费试用
更多热门智能应用
