答案：动态规划通过状态转移求解最优化问题，以LCS为例，定义dpi为两字符串前i和前j字符的最长公共子序列长度，若字符相等则dpi=dpi-1+1，否则dpi=max(dpi-1, dpi)，初始条件为边界全0；C++使用vector构建DP表并双重循环填充，最终返回dpm即为长度，可通过反向追踪还原LCS字符串，该方法适用于重叠子问题与最优子结构的场景。
动态规划（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 长度。
状态转移逻辑如下：
立即学习“C++免费学习笔记（深入）”；
- 如果 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。
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;
}
只需在主函数中调用该函数即可得到实际的LCS字符串。
基本上就这些。掌握状态定义、转移方程和边界处理，就能应对大多数经典DP问题，比如背包问题、编辑距离、最大子数组和等。关键在于把复杂问题拆解成可递推的小问题，并用表格避免重复计算。C++的vector和循环控制让实现变得简洁高效。
