> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/05-18-2022-1143.-longest-common-subsequence.md).

# 05/18/2022 1143. Longest Common Subsequence

1143\. Longest Common Subsequence

Method: use DP. This problem can be divided into subproblems. Create a 2d array DP, in which DP\[i]\[j] represents the longest common subsequence length.  Iterate from i = 1 and j = 1, If the current character at i-1 == character at j -1 , then we can set dp\[i]\[j] = di\[i-1]\[j-1] + 1. If it is not, then we need compare DP\[i]\[j-1] and DP\[i-1]\[j-1] to get the max value of it. Then finally return the DP\[m]\[n], where m is the length of text1 and n is the length of the text2.

Time O(m \* n)

Space O(m \* n)