> For the complete documentation index, see [llms.txt](https://liuxue2010.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://liuxue2010.gitbook.io/data-structure-and-algorithms/dynamic-programming-ii/longest-common-subsequence.md).

# Longest Common Subsequence

Given two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.

## Clarification

What's the definition of Longest Common Subsequence?

<https://en.wikipedia.org/wiki/Longest_common_subsequence_problem>

<http://baike.baidu.com/view/2020307.htm>

## Example

For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.

For "ABCD" and "EACB", the LCS is "AC", return 2.

## Solution

单序列型研究如何切，双序列型研究最后一个数字或者字母。

双序列型动态规划

图加上故事，非常有助于记忆。

abcd = abcd then f\[i - 1]\[j - 1] + 1

state: f\[i]\[j]代表了第一个sequence的前i个数字/字符，配上第二个sequence的前j个...\
function: f\[i]\[j] =研究第i个和第j个的匹配关系\
initialize: f\[i]\[0]和f\[0]\[i]

answer: f\[s1.length()]\[s2.length()]

state: f\[i]\[j]表示前i个字符配上前j个字符的LCS的长度\
function: f\[i]\[j] = MAX(f\[i-1]\[j], f\[i]\[j-1], f\[i-1]\[j-1] + 1) // a\[i] == b\[j]

\= MAX(f\[i-1]\[j], f\[i]\[j-1]) // a\[i] != b\[j] intialize: f\[i]\[0] = 0 f\[0]\[j] = 0

answer: f\[a.length()]\[b.length()]

```
class Solution:
    """
    @param A, B: Two strings.
    @return: The length of longest common subsequence of A and B.
    """
    def longestCommonSubsequence(self, A, B):
        # write your code here
        if len(A) == 0 or len(B) == 0:
            return 0
        # write your code here
        m = len(A) 
        n = len(B)

        f = [[0 for x in range(n + 1)] for y in range(m + 1)]

        f[0][0] = 0

        for i in range(1,m + 1):
            for j in range(1,n + 1):
                if A[i - 1] == B[j - 1]:
                    f[i][j] = f[i - 1][j - 1] + 1
                else:
                    f[i][j] = max(f[i-1][j],f[i][j-1])
        return f[m][n]
```