image.png

思路

它跟718的不同就在于
子序列可以不连续，子数组是连续的！
看下方图解，很清楚的思路
image.png
image.png

  1. var longestCommonSubsequence = function(text1, text2) {
  2.     // dp[i][j]是text1[0,i-1],text2[0,j-1]的最大公共子序列，包括两个端点
  3.     let dp =new Array(text1.length +1).fill(0).map(()=>new Array(text2.length+1).fill(0))
  5.     for(let i=1;i<=text1.length;i++){
  6.         for(let j=1;j<=text2.length;j++){
  7.             if(text1[i-1]===text2[j-1]){
  8.                 dp[i][j] =dp[i-1][j-1]+1
  9.             }else{
  10.                 dp[i][j] =Math.max(dp[i-1][j],dp[i][j-1])
  11.             }
  12.         }
  13.     }
  14.     //因为是不要求连续的子序列问题，那么最长的肯定是结尾的地方
  15.     return dp[text1.length][text2.length]
  16. };