c001. 10405 - Longest Common Subsequence -- UVa10405 | From: [106.1.117.161] | 發表日期 : 2024-10-08 01:02

1. 構造問題: 求解兩個字串 sa, sb 的最長共同子序列

2. 定義狀態: f(i, j) 表示 sa 的前 i 個字元和 sb 的前 j 個字元的最長共同子序列長度

3. 求解小規模的簡單問題:

    f(0, j) = 0 (for all j)

    f(i, 0) = 0 (for all i)

4. 狀態轉移方程式:

    f(i, j) =

    {

        sa[i] != sb[j]: max(f(i, j - 1), f(i - 1, j))

        sa[i] == sb[j]: f(i - 1, j - 1) + 1

    }

5. 判斷複雜度: O(n * m) n = sa.size(), m = sb.size();