动态规划（Dynamic Programming）

动态规划的特性

动态规划（DP）是一种解决最优化问题的方法，尤其适用于包含重叠子问题的场景。其核心思想是将复杂问题分解为更简单的子问题，通过记录子问题的解并合并，最终得到原问题的解。

DP的核心要素

最优子结构：局部最优解能够构成全局最优解，是解决问题的必要条件。

无后效性：前面状态和决策不会影响未来状态的决策。

空间换时间：通过存储子问题的解，减少重复计算，提高效率。

DP的四个步骤

划分阶段：将问题划分为若干阶段，并确保阶段有序。

确定状态与变量：为每个阶段定义状态，满足无后效性。

状态转移：根据相邻阶段的状态关系，建立转移方程。

边界条件：为转移方程提供终止条件。

最长公共子序列（LCS）的DP解法

LCS问题与LIS（Largest Incremental Sub-sequence）类似。通过对原字符串排序可以转换为求两个字符串的LCS。

解法思路

LCS问题：允许字符分离，求两个序列的最大交集。

LCS状态转移：

如果两个字符相等，LCS值为前一个字符的LCS值+1。

如果两个字符不等，LCS值为前一个字符或前面一字符的LCS值中的较大者。

代码实现

void lcs2(char *first, int lfirst, char *second, int lsecond) {    int *dir = new int[lfirst * lsecond];    int *dis = new int[lfirst * lsecond];        for(int i = 0; i < lfirst; i++) {        dis[i] = 0;        for(int j = 1; j < lfirst; j++) {            dis[j * lfirst] = 0;        }        for(int j = 1; j < lsecond; j++) {            if(first[i] == second[j]) {                dis[i + j * lfirst] = dis[(i-1) + (j-1)*lfirst] + 1;                dir[i + j * lfirst] = 0;            } else if(dis[i + (j-1)*lfirst] > dis[(i-1) + j * lfirst]) {                dis[i + j * lfirst] = dis[i + (j-1)*lfirst];                dir[i + j * lfirst] = 2;            } else {                dis[i + j * lfirst] = dis[(i-1) + j * lfirst];                dir[i + j * lfirst] = 1;            }        }    }    showLCS(first, dir, lfirst-1, lsecond-1, lfirst);    delete[] dir;    delete[] dis;}