付費限定文章

DP經典應用: 找出 最長共同子序列的長度 LCS_Leetcode #1143_Leetcode 精選75題解析

Jørgen Håland on Unsplash

這題也是滿經典的DP動態規劃教學案例和題目，就順便複習一下吧。

題目敘述

題目會給我們兩個字串text1, text2。

要求我們找出兩個字串的最長共同子序列，並且返回最長共同子序列的長度。

如果彼此沒有共同子序列，則返回0。

題目的原文敘述

測試範例

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.
abcde 和 ace 的最長共同子序列是ace
長度為3​

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
abc 和 abc 的最長共同子序列長度是 abc
長度為3​

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
abc 和 def 沒有共同子序列，無解，返回0

約束條件

Constraints:

• 1 <= text1.length, text2.length <= 1000

text1, text2的字串長度都介於1~1000之間。

• text1 and text2 consist of only lowercase English characters.

text1, text2都裡面都只會有小寫英文字母。

Dynamic programming的解題框架

再次複習Dynamic programming的解題框架，可分為三大步驟

1.定義狀態 [我在哪裡]

2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]

3. 釐清初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走，怎麼出發的]

1. 定義狀態 [我在哪裡]