动态规划
动态规划有时被称为递归的相反的技术。递归是从顶部开始将问题分解，通过解决所有分解小问题的方式，来解决整个问题。而动态规划这是从底部开始解决问题，将所有小问题解决掉，然后合并成整体的解决方案，从而解决掉整个大问题。递归方式虽然很简洁，但是效率不高，但是不能说递归是不好的，本质上是，命令式语言和面向对象的语言对递归的实现不够完善，因为它们没有将递归作为高级编程特性。
动态规划方案通常使用一个数组来建立一张表，用于存放被分解成众多子问题的解。当算法执行完毕，最终的解法将会在这个表中找到。
先来看看最经典的斐波那契数列的递归解法：
递归解法
function fib(n){
if(n < 2){
return n;
}else{
return fib(n - 1) + fib(n - 2);
}
}动态规划解法
function fibDyn(n) {
var temp = [];
for (var i = 0; i <= n; i++) {
temp[i] = 0
}
if (n < 2) {
return n;
} else {
temp[1] = 1;
temp[2] = 1;
for (var i = 2; i <= n; i++) {
temp[i] = temp[i - 1] + temp[i - 2];
}
return temp[i-1];
}
}还有个比较经典的动态规划问题，给定两个字符串,求出它们的最长公共字串
我们回顾一下动态规划的解题思路：
- 从底部开始解决问题，将所有小问题解决掉，然后合并成一个整体的解决方案。
- 使用一个数组建立一张表，用于存放被分解成众多子问题的解。
最小的是每个字符，所以要把分解成单个的字符去匹配每个单个的字符。思路如下
alt text
alt text
匹配为1，不匹配为0，这个时候我们就分解成为每个字符的匹配情况，由此得到。
function LCS(str1, str2) {
var arr = []
var maxLen = 0
var index = 0
for (var i = 0; i < str1.length; i++) {
arr[i] = []
for (var j = 0; j < str2.length; j++) {
arr[i][j] = 0
}
}
for (var i = 0; i < str1.length; i++) {
for (var j = 0; j < str2.length; j++) {
if (str1[i] == str2[j]) {
if (i == 0 || j == 0 || (str1[i - 1] != str2[j - 1])) {
arr[i][j] = 1
} else if (str1[i - 1] == str2[j - 1]) {
arr[i][j] = arr[i - 1][j - 1] + 1;
}
}
if (arr[i][j] > maxLen) {
maxLen = arr[i][j];
index = i;
}
}
}
if (maxLen == 0) {
return ""
} else {
var s = str1.slice(index+1-maxLen, index+1)
return s
}
}
var str1 = "abcdefg";
var str2 = "aczabcd";
LCS(str1, str2) // abcd本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-11-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录