构建dp数组，勇于解决问题

1.两个字符串比较

寻找最大公共字符串

这里迷糊的点在于，根据 s1 s2 的长度去生成 dp 举证的 的长宽怎么确定，以及 for 循环怎么写。
一开始纠结这一点，其实，去还原过程就可以轻松得到。
1）固定s1（长度m），拿 s2 （长度n）中的每一字符 依次和 s2 的每个字符比较。每个结果都记录，会生成arr[n][m]

  1. function getCommonString(s1, s2) {
  2.     let m = s1.length;
  3.     let n = s2.length;
  5.     let dp = new Array(n).fill().map(() => new Array(m).fill(0));
  7.     let max = 0;
  8.     let range = [-1, -1];
  9.     for (let i = 0; i < n; i++) {
  10.         for (let j = 0; j < m; j++) {
  11.             if (s1[i] === s2[j]) {
  12.                 if (i === 0 || j === 0) { // 边缘的处理，解决了纠结
  13.                     dp[i][j] = 1; 
  14.                 } else {
  15.                     dp[i][j] = dp[i - 1][j - 1] + 1; // 一开始看起来并不是动规，而是一种归类
  16.                 }
  18.                 if (max < dp[i][j]) {
  19.                     max = dp[i][j];
  20.                     range = [j + 1 - dp[i][j], j];
  21.                 }
  22.             }
  23.         }
  24.     }
  26.     return s1.slice(range[0], range[1] + 1);
  27. }

这个还是看不明白。
来个能看明白的：
不需要考虑太多，只要知道：1）s1 长度为m 指针为i; 2) s2 长度为 n 指针为 j;
2) dp 第一圈都填0，dp[i][j] 代表子问题：text1[0…i] 和 text2[0…j] 最大公共子字符串的长度

  1. function getCommonString(s1, s2) {
  2.     let m = s1.length + 1;
  3.     let n = s2.length + 1;
  5.     // dp[i][j] 代表 text1[0...i] 和 text2[0...j] 最大公共子字符串的长度
  7.     let dp = new Array(m).fill().map(() => new Array(n).fill(0));
  9.     for (let i = 0; i < m; i++) {
  10.         dp[i][0] = 0;
  11.     }
  13.     for (let j = 0; j < n; j++) {
  14.         dp[0][j] = 0;
  15.     }
  17.     let max = 0;
  18.     let end = 0;
  19.     for (let i = 1; i < m; i++) {
  20.         for (let j = 1; j < m; j++) {
  21.             if (s1[i - 1] === s2[j - 1]) {
  22.                 dp[i][j] = dp[i - 1][j - 1] + 1;
  23.                 if (max < dp[i][j]) {
  24.                     max = dp[i][j];
  25.                     end = i;
  26.                 }
  27.             }
  28.         }
  29.     }
  31.     return s1.slice(end - max, end);
  32.     // return s1.slice(end - max + 1, end + 1) // 注意要同时向回减一
  33. }

最长公共子序列

  1. function longestCommonSubsequence(text1, text2) {
  2.     let m = text1.length + 1;
  3.     let n = text2.length + 1;
  5.     // dp[i][j] 代表 text1[0...i] 和 text2[0...j] 最大公共子序列的长度
  6.     // 当 i = 0 时，text1[0...0] 代表 text1 的空子符串，因此 当 i = m，text1[0...m] 代表全部的 text1。
  7.     // 最终得出 dp.length 长度为 m + 1，而dp[0].length 为 n + 1。
  8.     let dp = new Array(m).fill().map(() => new Array(n).fill(0));
  10.     for (let i = 0; i < m; i++) {
  11.         dp[i][0] = 0;
  12.     }
  14.     for (let j = 0; j < n; j++) {
  15.         dp[0][j] = 0;
  16.     }
  18.     for (let i = 1; i < m; i++) {
  19.         for (let j = 1; j < n; j++) {
  20.             // dp[i][j] 代表 text1[0...i] 和 text2[0...j] 最大公共子序列的长度
  21.             // 所以当前字符表示为 text1[i - 1] 和 text2[j - 1]
  22.             if (text1[i - 1] === text2[j - 1]) { // 因为增加了边界，所以也要递减一个位置
  23.                 dp[i][j] = dp[i - 1][j - 1] + 1;
  24.             } else {
  25.                 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
  26.             }
  27.         }
  28.     }
  30.     return dp[m - 1][n - 1]; // 结尾元素
  31. }

image.png
数组认为加出一道边界哈。

5. 最长回文子串

72. 编辑距离

参考视屏: https://www.bilibili.com/video/BV1uv411W73P/?spm_id_from=333.788.recommend_more_video.0
子问题的发掘简直是叼炸天呢：
image.png
image.png
image.png
image.png

image.png

image.png
js 写法：

  1. var minDistance = function(word1, word2) {
  2.     const m = word1.length;
  3.     const n = word2.length;
  4.     const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
  5.     for (let i = 0; i <= m; i++) {
  6.         dp[i][0] = i;
  7.     }
  8.     for (let j = 0; j <= n; j++) {
  9.         dp[0][j] = j;
  10.     }
  12.     for (let i = 1; i <= m; i++) {
  13.         for (let j = 1; j <=n; j++) {
  14.             if (word1[i - 1] === word2[j - 1]) {
  15.                 dp[i][j] = dp[i - 1][j - 1];
  16.             } else {
  17.                 dp[i][j] = Math.min(dp[i][j - 1] + 1, dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1);
  18.             }
  19.         }
  20.     }
  22.     return dp[m][n];
  23. };

这题有点复杂了，但是作者还是很牛逼。