本文转自：知乎
作者：djh
在做文本相似度的时候遇到了动态规划这个概念。
这边做个简单的介绍，它原理概念和使用。
基本思路：
如果需要解决一个算法问题，而这个算法问题是由几个小问题有规律的组成的。动态规划的思路是通过解决最小的问题，然后存储最小问题的解，然后在解答上一级问题的时候就可以直接使用这个解，因此可以轻松的解决这个算法问题，动态规划的核心是从低至上解决问题。
问题举例：
斐波那契数列求解：
f(n) = f(n - 1) + f(n - 2)
这个数列的求解我们早就学过了，可以用一个简单的递归就解决了，如下。
public int f(int n) {
if(n<=0)
return 0;
if(n==1)
return 1;
return f(n-1)+f(n-2);
} 我们画出这个n = 6 的斐波那契数列计算过程的递归树形结构，大概是这样子的。最后答案是8.
动态规划的思想是从 f(1) f(2) 开始。从底层一步一步往上计算，算法如下：
public static int f(int n) {
if(n<=0)
return n;
int * p=new int[n+1];
p[0]=0;
p[1]=1;
for(int i=2;i<=n;i++)
{
p[i]=p[i-1]+p[i-2];
}
return p[n];
} 最小编辑距离问题：
两个字符串之间存在差异，例如abcd 和 acd，或者happy 和 huppy ，如何通过最小的手段让两个字符一样。可以用的操作为，插入，删除和替换。
动态规划思路解决这个问题：两个字符串可以看出两个数组，str1 str2，从str1[0] 和str2[0] 开始比较，然后从一个方向引申，使用前面已有的数据进行分析。这样讲比 较抽象用一个图来表示会比较清楚。
假设两个数组分别是 abcd 和 acd，如下排布
先初始化数组序列
现在我们要开始做动态规划
先比较str1[0] 和 str2[0] 然后比较 str1[1] 和 str2[0] 就是横向比较，然后再跳到下一行横向比较，然后就是说，比较来干嘛，比较如果两个字符相等就取对角线的值，如果不相等就取周围三个最小的值加+1。比如我们现在要填的第一个值， a == a 那么就填写对角线的 0。
这一次，a ！= b 了，查看周围三个地方，最小的值加+1
以此类推, 到第二列也是一样的。
填到这个值的时候，发现c == c 就填充对角线的。一直这样到最后
最后这个值就是我们需要的解。那么代码怎么写：如下
/**
* 动态规划算法
* @param {string} a
* @param {string} b
* @returns {number} 从 a → b 的最小编辑距离 */
function dynamicPlanning(a, b) {
let lenA = a.length;
let lenB = b.length;
let d = [];
d[0] = [];
for (let j = 0; j <= lenB; j++) {
d[0].push(j);
}
for (let i = 0; i <= lenA; i++) {
if (d[i]) {
d[i][0] = i;
} else {
d[i] = [];
d[i][0] = i;
}
}
for (let i = 1; i <= lenA; i++) {
for (let j = 1; j <= lenB; j++) {
if (a[i - 1] === b[j - 1]) {
d[i][j] = d[i - 1][j - 1];
} else {
let m1 = d[i - 1][j] + 1;
let m2 = d[i][j - 1] + 1;
let m3 = d[i - 1][j - 1] + 1;
d[i][j] = Math.min(m1, m2, m3);
}
}
}
return d[lenA][lenB];
} 其他
关注我不迷路，目前只是一些入门级的小文章，后面会有AI系列文章推送。
https://github.com/yazone/ai_learning_path更多嵌入式AI技术相关内容请关注嵌入式AI专栏。
