C++怎么实现一个动态规划算法_C++解决最长公共子序列(LCS)等经典DP问题

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

C++怎么实现一个动态规划算法_C++解决最长公共子序列(LCS)等经典DP问题

2025-11-22

浏览次数：次

返回列表

答案：动态规划通过状态转移求解最优化问题，以LCS为例，定义dpi为两字符串前i和前j字符的最长公共子序列长度，若字符相等则dpi=dpi-1+1，否则dpi=max(dpi-1, dpi)，初始条件为边界全0；C++使用vector构建DP表并双重循环填充，最终返回dpm即为长度，可通过反向追踪还原LCS字符串，该方法适用于重叠子问题与最优子结构的场景。

c++怎么实现一个动态规划算法_c++解决最长公共子序列(lcs)等经典dp问题

动态规划（Dynamic Programming，简称DP）是C++中解决最优化问题的重要方法，尤其适用于具有重叠子问题和最优子结构性质的问题。最长公共子序列（LCS）就是典型的例子。下面以LCS为例，说明如何用C++实现一个动态规划算法。

理解LCS问题

给定两个字符串 str1 和 str2，找出它们的最长公共子序列的长度。子序列不要求连续，但要保持字符在原串中的相对顺序。

例如：
str1 = "ABCDGH"
str2 = "AEDFHR"
LCS 是 "ADH"，长度为 3。

定义状态与状态转移方程

使用二维数组 dp[i][j] 表示 str1 的前 i 个字符和 str2 的前 j 个字符的 LCS 长度。

状态转移逻辑如下：

如果 str1[i-1] == str2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])

初始条件：dp[0][j] = 0，dp[i][0] = 0，表示空串与任何串的 LCS 为 0。

CA.LA

第一款时尚产品在线设计平台，服装设计系统

94 查看详情 CA.LA

C++代码实现

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int longestCommonSubsequence(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();

    // 创建二维DP表
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // 填充DP表
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1[i-1] == str2[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 s1 = "ABCDGH";
    string s2 = "AEDFHR";
    cout << "LCS Length: " << longestCommonSubsequence(s1, s2) << endl;
    return 0;
}

输出LCS字符串本身

如果不仅要长度，还想还原出具体的子序列，可以从 dp[m][n] 开始反向追踪：

string getLCSString(string str1, string str2, vector<vector<int>>& dp) {
    string lcs = ";";
    int i = str1.length(), j = str2.length();

    while (i > 0 && j > 0) {
        if (str1[i-1] == str2[j-1]) {
            lcs = str1[i-1] + lcs;
            i--; j--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }
    return lcs;
}