动态规划_最长公共子序列

'示例 1:输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace"，它的长度为 3。
'示例 2: 输入：text1 = "abc", text2 = "abc" 输出：3 解释：最长公共子序列是 "abc"，它的长度为 3。
'示例 3: 输入：text1 = "abc", text2 = "def" 输出：0 解释：两个字符串没有公共子序列，返回 0。


Sub d44_动态规划_最长公共子序列()
    Dim dp(), text1, text2, len1, len2
    text1 = "abcdefg"
    text2 = "cdef"
    len1 = Len(text1)
    len2 = Len(text2)
    ReDim dp(len1, len2)
    For i = 1 To Len(text1)
        char1 = Mid(text1, i, 1)
        For j = 1 To Len(text2)
            char2 = Mid(text2, j, 1)
            If char1 = char2 Then
                dp(i, j) = dp(i - 1, j - 1) + 1
            Else
                dp(i, j) = Application.Max(dp(i - 1, j), dp(i, j - 1))
            End If
        Next
    Next
    Debug.Print (dp(Len(text1), Len(text2)))
End Sub