leetcode 1143.最長共通部分列（動的計画法）

Leetcode 1143 Longest Common Subsequence

2つの文字列text1とtext2を指定すると、2つの文字列の最長共通部分列を返します。

サブシーケンスは、新しい文字列の文字列を参照します。これは、文字の相対的な順序を変更せずに、元の文字列を一部の文字で削除した後の新しい文字列です（または、文字を削除しない場合があります）。

たとえば、「ace」は「abcde」サブシーケンスですが、「aec」は「abcde」サブシーケンスよりも優れています。 'common subsequence'の2つの文字列は、2つの文字列に共通するサブシーケンスです。

2つの文字列が共通でない場合、サブシーケンス0が返されます。

例1：

入力：text1 = 'abcde'、text2 = 'ace'

出力：3

解釈：最長共通部分列は「ace」であり、その長さは3です。

例2：

入力：text1 = 'abc'、text2 = 'abc'

出力：3

解釈：最長共通部分列は「abc」であり、その長さは3です。

例3：

入力：text1 = 'abc'、text2 = 'def'

出力：0

説明：2つのストリングは共通のサブシーケンスではなく、0が返されます。

促す：

1<= text1.length <= 1000

1<= text2.length <= 1000

入力文字列には小文字のみが含まれます。

解決： https://leetcode-cn.com/problems/longest-common-subsequence/solution/chao-xiang-xi-dong-tai-gui-hua-jie-fa-by-shi-wei-h/

class Solution { public: int longestCommonSubsequence(string text1, string text2) { int len1 = text1.size() int len2 = text2.size() if(len1==0 || len2==0) return 0 vector dp(len1+1,vector (len2+1,0)) for(int i=1i<=len1++i) for(int j=1j<=len2++j) { dp [i] [j] = max3 (dp [i-1] [j], dp [i] [j-1], dp [i-1] [j-1] + (text1 [i-1] = = text2 [j-1])) // note is the subscript i-1 text1 } return dp[len1][len2] } int max3(int i,int j,int k){ return max(i,max(j,k)) } }