在工作中，我们都用过递归，用俗话说就是函数自己调用自己；而动态规划一般被认为是和递归相反的一种解决问题的思路：递归是从解决一个大问题开始，通过逐步解决一些小问题，来使最终的问题得到解决；动态规划的思路则恰恰相反。
我们直接来看一些例子，大家有时间可以仔细揣摩，代码有不妥的地方，多交流。
斐波拉契数列
我们先看使用递归的方式。
// 递归求斐波拉契数列
function recurFib (n) {
if (2 > n) return n;
return recurFib(n - 1) + recurFib(n - 2);
}
console.group('递归')
var time = Date.now();
console.log(recurFib(30));
console.log(Date.now() - time);
console.groupEnd()再看使用动态规划的思路。
// 动态规划
function dpFib (n) {
var arr = [0, 1]
if (n < 2) return arr[n]
for (var i = 2; i <= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}
console.group('动态规划')
var time2 = Date.now();
console.log(dpFib(30));
console.log(Date.now() - time2);
console.groupEnd()递归的代码十分简洁，但是效率很低，因为每一次都要重复进行计算，除非把一些中间结果保存下来；动态规划的代码效率很高，通过数组把一些中间值保存下来了。
顺带再看看使用循环的思路。
// 迭代
function iterFib (n) {
if (2 > n) return n;
var last = 1;
var lastLast = 0;
var now;
for (var i = 2; i <= n; i++) {
now = last + lastLast;
lastLast = last;
last = now;
}
return now;
}
console.group('迭代')
var time2 = Date.now();
console.log(iterFib(30));
console.log(Date.now() - time2);
console.groupEnd()通过这几个例子，可以鲜明地感受到动态规划的思路的独特之处。再来看看其他动态规划的例子。
获取最长公共子串
比如说，两个字符串 “addcc” 和 “bddcc”，他们之间最长的相似字符是“ddcc”，怎么实现这个解法呢？
先看暴力破解的方式。
// 寻找最长公共子串，暴力解法
function longCompareStr(s1, s2) {
var index = 0; // 索引位置
var long = 0; // 总长度
var tempIndex = 0; // 临时索引位置
var tempLong = 0; // 临时长度
for(var i = 0; i < s1.length; i++) {
for(var j = 0; j < s2.length; j++) {
if (s1[i] == s2[j]) { // 找到第一次相同的位置
tempIndex = i; // 记录当前的索引位置
tempLong++; // 长度加 1
for(var k = 1; k < s1.length - i; k++) { // 再往下比对
if (s1[i+k] == s2[j+k]) {
tempLong++;
} else {
break;
}
}
if (tempLong > long) {
index = tempIndex;
long = tempLong;
}
tempLong = 0;
}
}
}
return s1.slice(index, index + long);
}
console.group('寻找最长公共子串');
console.log(longCompareStr('bccaqwerty', 'bbccqwerty2'));
console.groupEnd();再看使用动态规划的例子。
// 使用动态规划
function dpLongCompareStr (s1, s2) {
var index = 0; // 索引值位置
var long = 0; // 最长相等的字符数
var arr = [];
for (var i = 0; i < s1.length; i++) {
arr[i] = []
for (var j = 0; j < s2.length; j++) {
arr[i][j] = 0;
}
} // 以上代码初始化二维数组
for (var i = 0; i < s1.length; i++) {
for (var j = 0; j < s2.length; j++) {
if (s1[i] == s2[j]) {
if (i > 0 && j > 0) {
arr[i][j] = arr[i - 1][j - 1] + 1 // 核心代码
} else {
arr[i][j] = 1
}
}
if (arr[i][j] > long) {
long = arr[i][j];
index = i - long + 1; // 为什么要 +1，因为当 i = 0；long = 1；时，index = -1 不合理
}
}
}
console.log(arr)
return s1.slice(index, index + long) || null;
}
console.group('寻找最长公共子串 --- 动态规划');
console.log(dpLongCompareStr('adfsfdfsd', 'adfsfsdfsdf'));
console.groupEnd();啊，代码有点多，我又懒于讲解，还是仔细看代码吧。总之，使用递归可以解决的问题，也可以使用动态规划的思路去解决，而且效率更高，但是需要保持临时的计算结果。
下面是所有的代码，包含了经典的背包问题。
See the Pen 动态规划的相关例子和代码 by zeng (@zengxiaoluan) on CodePen.
LeetCode 第 70 题，也是一个动态规划的例子，可以参考学习下。
参考链接
https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92
