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

#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;
}

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;
}