algo/di-er-zhan-a01c6/zi-xu-lie--6bc09/jing-dian--93b6b/

[giscus[bot]]

algo/di-er-zhan-a01c6/zi-xu-lie--6bc09/jing-dian--93b6b/

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 限时附赠网站会员！ 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 :----: :----: :----: 1143. Long...

https://labuladong.github.io/algo/di-er-zhan-a01c6/zi-xu-lie--6bc09/jing-dian--93b6b/

[shiboys]

「好好体会，多多联系」是点睛之笔的结尾！

[hammajang]

这篇文章被锁了TnT，但看了编辑距离的解法后写出来了，跟编辑距离就一个地方不同：i、j指针指向的元素不相同/相同时的操作不一样
Java代码：
class Solution {
int [][] memo;
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(),n = text2.length();
memo = new int[m][n];
for(int [] row : memo)
Arrays.fill(row,-1);
return dp(text1,m-1,text2,n-1);
}
//dp函数定义：返回s1[0..i] s2[0..j]的最长公共子序列
int dp(String s1,int i,String s2,int j){
if(i == -1)
return 0;
if(j == -1)
return 0;
if(memo[i][j] != -1)
return memo[i][j];

    if(s1.charAt(i) == s2.charAt(j))
        return dp(s1,i - 1,s2,j - 1) + 1;
    
    memo[i][j] = max(
        dp(s1,i - 1,s2,j),
        dp(s1,i,s2,j - 1)
    );

    return memo[i][j];
}

int max(int a,int b){
    return Math.max(a,b);
}

}