1143. 最长公共子序列

思路

dp：代表两个字符串0-i、0-j所包含的最长公共子序列

dp[i][0]、dp[0][j] 代表其中任一字符串为空时的公共子序列，自然是0 为了方便，初始化dp为0

遍历两个字符串：

当text1[i]==text2[j]时，当前字符相同，此时的最长公共子序列长度=text1[0:i]、text2[0:j]（0~ i-1、0~j-1 ）之间最长公共子序列+1

text1[0:i]、text2[0:j]是代表 0~ i-1、0~j-1 （字符串的截取s[i:j]取不到j位置的字符，而是j-1）

当text1[i]!=text2[j]时,当前0~ i、0~j最长公共子序列为下方最长公共序列

1.0~ i-1、0~j最长公共子序列

2.0~ i、0~j-1 最长公共子序列

3.0~ i-1、0~j-1 最长公共序列

class Solution(object):def longestCommonSubsequence(self, text1, text2):""":type text1: str:type text2: str:rtype: int"""if text1==text2:return len(text1)dp=[[0]*(len(text2)+1) for i in range(len(text1)+1)]##行、列要跟dp定义对上for i in range(len(text1)):for j in range(len(text2)):if text1[i]==text2[j]:#当前字符相等，则找0~i-1、0~j-1最长公共序列+1  (1为当前字符)dp[i+1][j+1]=dp[i][j]+1else:'''当前字符不相等，当前0~i、0~j最长公共子序列为下方最长公共序列：1.0~i-1、0~j最长公共子序列2.0~i、0~j-1 最长公共子序列3.0~i-1、0~j-1 最长公共序列'''dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j],dp[i][j])return dp[-1][-1]