【动态规划】1143. 最长公共子序列
2024-01-02 17:20:10
1143. 最长公共子序列
解题思路
- dp[i][j] 表示序列s1[0,i-1] 和s2[0,j-1]之间的公共长度
- 当前字符s1[i]和s2[j]相同的话 那么memo[i][j] = memo[i - 1][j - 1] + 1;
- 如果不同, memo[i][j] = Math.max(memo[i][j - 1],memo[i - 1][j]);
class Solution {
int[][] memo;
public int longestCommonSubsequence(String text1, String text2) {
// dp[i][j] 表示序列s1[0,i-1] 和s2[0,j-1]之间的公共长度
memo = new int[text1.length() + 1][text2.length()+1];
// base case
// 第一行和第一列 全部初始化为0 因为没有公共序列
int m = text1.length();
int n = text2.length();
return dp(text1,text2,m,n);
}
int dp(String text1,String text2,int m,int n){
if(m < 0 || n < 0){
return 0;
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(text1.charAt(i - 1) == text2.charAt(j - 1)){
// 表示该公共字符一定在lcs中 将之前的值 + 1
memo[i][j] = memo[i - 1][j - 1] + 1;
}else{
// 当前字符不在lcs中 选取最大的
memo[i][j] = Math.max(memo[i][j - 1],memo[i - 1][j]);
}
}
}
return memo[m][n];
}
}
文章来源:https://blog.csdn.net/qq_44653420/article/details/135343151
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!