C++動態規劃怎么實現查找最長公共子序列

C++動態規劃怎么實現查找最長公共子序列

1. 什么是動態規劃

動態規劃（Dynamic Programming，簡稱DP）是一種分階段求解問題的算法思想。它將復雜問題分解為多個子問題，通過求解子問題的最優解來得到原問題的最優解。動態規劃常用于解決最優化問題，如最長公共子序列、最短路徑等。

2. 什么是最長公共子序列

最長公共子序列（Longest Common Subsequence，簡稱LCS）是指在兩個或多個序列中，按順序出現的最長的子序列。子序列不要求連續，但必須保持相對順序。

例如，序列ABCBDAB和BDCAB的最長公共子序列是BCAB，長度為4。

3. 動態規劃求解最長公共子序列的思路

動態規劃求解最長公共子序列的核心思想是構建一個二維數組dp，其中dp[i][j]表示序列X的前i個字符和序列Y的前j個字符的最長公共子序列的長度。

3.1 狀態轉移方程

• 如果X[i-1] == Y[j-1]，則dp[i][j] = dp[i-1][j-1] + 1。
• 如果X[i-1] != Y[j-1]，則dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

3.2 初始化

• dp[0][j] = 0，表示空序列與Y的前j個字符的最長公共子序列長度為0。
• dp[i][0] = 0，表示X的前i個字符與空序列的最長公共子序列長度為0。

3.3 最終結果

dp[m][n]即為序列X和Y的最長公共子序列的長度，其中m和n分別為X和Y的長度。

4. C++實現

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length();
    int n = text2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}

int main() {
    string text1 = "ABCBDAB";
    string text2 = "BDCAB";
    int result = longestCommonSubsequence(text1, text2);
    cout << "The length of the longest common subsequence is: " << result << endl;
    return 0;
}

4.1 代碼解釋

• dp數組的大小為(m+1) x (n+1)，其中m和n分別為兩個輸入字符串的長度。
• 雙重循環遍歷dp數組，根據狀態轉移方程更新dp[i][j]的值。
• 最終返回dp[m][n]，即最長公共子序列的長度。

4.2 輸出結果

運行上述代碼，輸出結果為：

The length of the longest common subsequence is: 4

5. 總結

通過動態規劃的方法，我們可以高效地求解兩個序列的最長公共子序列問題。該方法的時間復雜度為O(m*n)，空間復雜度為O(m*n)，其中m和n分別為兩個序列的長度。

在實際應用中，最長公共子序列問題常用于文本比較、基因序列分析等領域。掌握動態規劃的思想和實現方法，對于解決類似的復雜問題具有重要意義。