1. // 暴力法
    2.         function lcs(s, t) {
    3.             if(s === '' || t === ''){
    4.                 return 0;
    5.             }
    6.             if(s[s.length - 1] === t[t.length-1]){
    7.                 return lcs(
    8.                     s.substr(0, s.length - 1),
    9.                     t.substr(0, t.length - 1))+1
    10.             }else{
    11.                 return Math.max(
    12.                     lcs(s.substr(0, s.length - 1), t),
    13.                     lcs(s, t.substr(0, t.length - 1))
    14.                 )
    15.             }
    16.         }
    17.         // 动态规划
    18.         function lcs(s, t){
    19.             const dp = []
    20.             for(let y=0; y<=t.length; y++){
    21.                 dp[y] = []
    22.                 for(let x = 0; x <= s.length; x++){
    23.                     if(x === 0 || y === 0){
    24.                         dp[y][x] = 0
    25.                     }else  if(s[x-1] === t[y-1]){
    26.                         dp[y][x] = dp[y-1][x-1] + 1
    27.                     }else{
    28.                         dp[y][x] = Math.max(
    29.                             dp[y-1][x], dp[y][x-1]
    30.                         )
    31.                     }
    32.                 }
    33.                 console.log(dp)
    34.             }
    35.             return dp[t.length][s.length]
    36.         }
    37.         console.log(lcs('BANANA', 'ATANA'))