动态规划之最长公共子序列

发表于 |

动态规划求最长公共子序列的js实现

动态规划类似于递推算法，典型的动态规划模型–斐波那契数列，可以用递归来实现，但是耗费内存空间比较大，如果不做任何缓存优化，计算1000个数的时候基本就很耗费时间了，尽管可以在递归的过程中，用一个cache数组缓存已经算出的值，但是函数的嵌套带来的内存开销也会影响，es6的尾调用优化很好的解决了函数嵌套带来的内存溢出问题。但是真正的精髓算法还是属于动态规划。

最长公共子序列也是如此，直接看代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function lcs(word1, word2) {
  var max = 0;
  var index = 0;
  var lcsarr = new Array(word1.length + 1);
    for (var i = 0; i <= word1.length + 1; ++i) {
      lcsarr[i] = new Array(word2.length + 1);
      for (var j = 0; j <= word2.length + 1; ++j) {
        lcsarr[i][j] = 0;
      }
    }
    for (var i = 1; i <= word1.length; ++i) {
      for (var j = 1; j <= word2.length; ++j) {
        if (word1[i - 1] == word2[j - 1]) {
          lcsarr[i][j] = lcsarr[i - 1][j - 1] + 1;
        } else {
          lcsarr[i][j] = 0;
        }
        if (max < lcsarr[i][j]) {
          max = lcsarr[i][j];
          index = i;
        }
      }
    }
    var str = "";
    if (max == 0) {
      return "";
    } else {
      for (var i = index - max; i < index; ++i) {
        str += word1[i];
      }
    return str;
    }
}