动态规划是很多算法（例如KMP算法）的基础，有很多的应用场景，其核心原理为：通过前面一个或者几个状态推算出后一个状态，往往使用迭代来求出最优解。求最长公共子串 LCS（longest common substring）是动态规划的典型应用。
求 LCS 的普通算法：
/**
* @param {Array/String} 数组1
* @param {Array/String} 数组1
* @return {Array/String} 最大连续的公共子串
*/
function getLCS(arr1, arr2) {
var sub = arr1 instanceof Array ? [] : '';
if (!arr1.length || !arr2.length) {
return sub;
}
var maxSize = 0;
var preSize = 0;
var index = -1;
for (var i = 0; i < arr1.length; i++) {
var preIndex = i;
//以i为首的arr1子串与arr2中的每个子串比较
for (var j = 0; j < arr2.length; j++) {
if (arr1[preIndex] == arr2[j]) {
preIndex++;
preSize++;
if (preSize > maxSize) {
maxSize = preSize;
index = j;
}
} else {
preIndex = i;
preSize = 0;
}
}
}
if (index > -1) {
sub = arr2.slice(index - maxSize + 1, index + 1);
}
return sub;
}
动态规划中有三个概念：边界、最优子结构、状态转移公式。
对于求 LCS 的问题，设两个字符串分别为 a 和 b ，a 的长度为 m，b 的长度为 n。其状态转移公式可用如下表示：
- dp(0,0) = 0 (a[0]!=b[0])
- dp(0,0) = 1 (a[0]==b[0])
- dp(i,j) = dp(i-1,j-1) + 1 (a[i] == b[j])
- dp(i,j) = 0 (a[i] != b[j])
在这个方程中，1和2为边界，3为最优子结构。
动态规划求 LCS 的算法:
/**
* @param {Array/String} 数组1
* @param {Array/String} 数组1
* @return {Array/String} 最大连续的公共子串
*/
function getLCS(arr1, arr2) {
var sub = arr1 instanceof Array ? [] : '';
if (!arr1.length || !arr2.length) {
return sub;
}
var maxSize = 0;
var preDp = [];
var dp = null;
var index = -1;
for (var i = 0; i < arr1.length; i++) {
dp = [];
for (var j = 0; j < arr2.length; j++) {
dp[j] = 0;
if (arr1[i] == arr2[j]) {
dp[j] = (preDp[j - 1] || 0) + 1;
if (dp[j] > maxSize) {
maxSize = dp[j];
index = j;
}
}
}
//保存i行的结果，供i+1行使用
preDp = dp;
}
if (index > -1) {
sub = arr2.slice(index - maxSize + 1, index + 1);
}
return sub;
}