d231. 97北縣賽-2-基因序列密碼問題 -- 97學年度北基區資訊學科能力競賽 | From: [106.1.117.161] | 發表日期 : 2024-10-20 23:35

1. 構造問題: s1, s2 的最長共同子序列

2. 定義狀態: f(i, j) = s1[:i] 和 s2[:j] 的最長共同子序列

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

   f(i, 0) = ""

   f(0, j) = ""

4. 狀態轉移方程式:

    f(i, j) =

    {

        if s1[i] == s2[j] : f(i - 1, j - 1) + s1[i];

        else: 選擇 f(i - 1, j), f(i, j - 1) 比較長的

    }

5. 判斷複雜度: O(n^2)