1. 线性DP 1143. 最长公共子序列

最经典双串：

1143. 最长公共子序列 (LCS)  https://leetcode-cn.com/problems/longest-common-subsequence/submissions/

func longestCommonSubsequence(text1 string, text2 string) int {
    //最长公共子串
    n1,n2 := len(text1),len(text2)
    //text2是内 
    dp := make([][]int,n2+1)
    for i:=0;i<=n2;i++{
        dp[i] = make([]int,n1+1)
    }
    for i:=1;i<=n2;i++{
        for j:=1;j<=n1;j++{
            if text2[i-1] == text1[j-1]{
                dp[i][j]= dp[i-1][j-1]+1
            }else{
                dp[i][j] = MAX(dp[i-1][j],dp[i][j-1])
            }            
        }
    }
    return dp[n2][n1]
}

func MAX(i,j int) int{
    if i<j{
        return j
    }else{
        return i
    }
}