1143.最长公共子序列

一.　　题目描述：

　　https://leetcode-cn.com/problems/longest-common-subsequence/

二.　　动态规划解法

例如：s1="abcde"　　s2= "ace"，求两个字符串的公共子序列，答案是“ace”

1.　S{s1,s2,s3....si} T{t1,t2,t3,t4....tj}

2.　子问题划分

(1) 如果S的最后一位等于T的最后一位，则最大子序列就是{s1,s2,s3...si-1}和{t1,t2,t3...tj-1}的最大子序列+1

(2) 如果S的最后一位不等于T的最后一位，那么最大子序列就是

① {s1,s2,s3..si}和 {t1,t2,t3...tj-1} 最大子序列

② {s1,s2,s3...si-1}和{t1,t2,t3....tj} 最大子序列

以上两个自序列的最大值

3.　边界

只剩下{s1}和{t1}，如果相等就返回1，不等就返回0

4.　使用一个表格来存储dp的结果

如果 S[i] == T[j] 则dp[i][j] = dp[i-1][j-1] + 1

否则dp[i][j] = max(dp[i][j-1],dp[i-1][j])

最后返回结果dp[i][j] = 3; 

1143.最长公共子序列

原文：https://www.cnblogs.com/da-peng/p/11629497.html