第3章复杂动态规划

🎯 本章学习目标

通过本章的学习，你将能够：

掌握二维DP：理解二维动态规划的状态定义和转移，解决网格路径等问题
精通LIS：熟练掌握最长上升子序列的 O(n²) 解法
精通LCS：熟练掌握最长公共子序列的二维DP解法
理解区间DP：掌握区间DP的基本思想和枚举顺序
掌握滚动数组优化：理解滚动数组原理，能进行空间优化
理解记忆化搜索：知道记忆化搜索和递推DP的关系
分析DP复杂度：能计算DP的时间和空间复杂度
区分子序列和子串：清楚子序列和子串的区别
掌握DP解题四步：定状态、找转移、定初始、定顺序
应对真题题型：能解决选择、判断、编程等各类DP题目

🗺️ 本章知识图谱

复杂动态规划
├── DP 基础回顾
│   ├── 最优子结构
│   ├── 重叠子问题
│   └── DP 解题四步：定状态、找转移、定初始、定顺序
├── 二维 DP
│   ├── 网格路径计数
│   │   ├── dp[i][j] = 走到(i,j)的方案数
│   │   ├── dp[i][j] = dp[i-1][j] + dp[i][j-1]
│   │   └── 边界：第一行/第一列为1
│   └── 二维最值问题
├── LIS 最长上升子序列
│   ├── 定义：子序列（不要求连续），严格上升
│   ├── O(n²) 解法
│   │   ├── dp[i] = 以i结尾的LIS长度
│   │   ├── dp[i] = max(dp[j]+1), j<i 且 a[j]<a[i]
│   │   └── 答案 = max(dp[i])
│   └── O(n log n) 优化（了解）
├── LCS 最长公共子序列
│   ├── 定义：两个序列的公共子序列
│   ├── dp[i][j] = a前i个和b前j个的LCS长度
│   ├── 转移方程
│   │   ├── a[i-1]==b[j-1]：dp[i][j]=dp[i-1][j-1]+1
│   │   └── 不等：dp[i][j]=max(dp[i-1][j], dp[i][j-1])
│   └── 答案 = dp[n][m]
├── 区间 DP
│   ├── 特点：大区间依赖小区间
│   ├── 枚举顺序：先枚举长度，再枚举起点
│   ├── dp[l][r] = 区间[l,r]的最优解
│   └── 典型：石子合并、回文子串
├── 滚动数组优化
│   ├── 原理：只需要上一行/前一个状态
│   ├── 空间从 O(n²) 降到 O(n)
│   ├── 01背包：一维数组，j逆序
│   └── LCS：可优化到 O(min(n,m))
├── 记忆化搜索
│   ├── 递归 + 记忆化（memo）
│   ├── 等价于递推DP
│   └── 适合：状态转移复杂、边界情况多
└── 易错点
    ├── LIS答案是max(dp)，不是dp[n-1]
    ├── 01背包一维化要逆序
    ├── 子序列 vs 子串
    └── 区间DP枚举顺序

一、📋 考纲原文与考点全景图

据CCF官方七级考纲：

掌握复杂动态规划（二维动态规划、动态规划最值优化）。包括区间动态规划、最长上升子序列（LIS）、最长公共子序列（LCS）等内容，理解基于滚动数组等降低动态规划空间复杂度的方法。

考点	难度	选择/判断出现频率	编程题出现频率
二维动态规划（网格路径）	⭐⭐	高	中
区间DP（石子合并等）	⭐⭐⭐	中	高
LIS（最长上升子序列）	⭐⭐	极高	中
LCS（最长公共子序列）	⭐⭐⭐	高	中
滚动数组优化	⭐⭐⭐	高	高
记忆化搜索↔递推转换	⭐⭐	中	中

二、动态规划基础回顾 🧱

1.1 DP三要素

要素	含义	一句话理解
状态定义	用什么变量描述子问题	"我在哪、已经做了什么"
状态转移方程	大问题如何由小问题推出	"从哪里来"
边界条件	最小子问题的答案	"起点在哪"

1.2 两大前提性质

最优子结构：大问题的最优解，可以由小问题的最优解组合而来。
无后效性：当前状态确定后，未来的决策不依赖"是怎么走到当前状态的"。

⚠️ 易错提醒：考试判断题常考"动态规划一定具有多项式时间复杂度"——这是错误的！背包问题的时间复杂度与容量V有关，V很大时是伪多项式复杂度。2025年9月GESP七级单选第10题就考了这一点（选项"采用动态规划的算法一定具有多项式时间复杂度"为错误项）。

三、二维动态规划 📊

2.1 网格路径计数/最值

经典问题：在一个 m×n 的网格中，从左上角走到右下角，每次只能向右或向下，求路径数 / 最小路径和。

状态定义：dp[i][j] 表示到达格子 (i, j) 的路径数（或最小路径和）。

状态转移（路径计数）：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

状态转移（最小路径和）：

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

📝 2025年3月GESP七级真题第13题就考了最小路径和的状态转移方程填空，正确答案为 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。

✅ 完整代码模板：最小路径和

cpp

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

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    
    dp[0][0] = grid[0][0];
    // 第一行：只能从左边来
    for (int j = 1; j < n; j++)
        dp[0][j] = dp[0][j-1] + grid[0][j];
    // 第一列：只能从上面来
    for (int i = 1; i < m; i++)
        dp[i][0] = dp[i-1][0] + grid[i][0];
    // 一般情况
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
    
    return dp[m-1][n-1];
}

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> grid(m, vector<int>(n));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> grid[i][j];
    cout << minPathSum(grid) << endl;
    return 0;
}

2.2 背包问题的二维形式

0/1背包：n个物品，每个有重量w[i]和价值v[i]，背包容量为W，每个物品选或不选，求最大价值。

二维状态定义：dp[i][j] 表示前i个物品、容量为j时的最大价值。

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

📝 **2024年12月GESP七级编程题"武器购买"**是 0/1 背包的典型应用；**2025年9月GESP七级编程题2"金币收集"**则是排序 + 最长上升子序列（LIS）类的线性 DP（金币按坐标排序、用偏移量把"可达"转为 LIS，而非选或不选的背包结构）。2025年6月七级编程题2"调味平衡"则是背包+偏移量的差值DP。

四、LIS（最长上升子序列）📈

3.1 问题定义

给定序列 A，找到最长的严格递增子序列的长度。注意：子序列不要求连续，但要求保持原序。

示例：A = [10, 9, 2, 5, 3, 7, 101, 18]，LIS长度为 4（如 [2, 3, 7, 101] 或 [2, 5, 7, 18]）。

3.2 O(n²) 朴素DP写法

状态定义：dp[i] 表示以 a[i] 结尾的最长上升子序列长度。

状态转移：

dp[i] = max(dp[j] + 1)  对所有 j < i 且 a[j] < a[i]

💡 为什么状态要包含"以a[i]结尾"？ 因为只有确定了最后一个数字是谁，才能判断下一个数字能否接在后面（必须比它大才能接）。

✅ 完整代码模板：LIS O(n²)

cpp

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

const int MAXN = 10005;
int a[MAXN], dp[MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        dp[i] = 1; // 初始化：每个元素本身就是长度为1的上升子序列
    }
    
    int ans = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    
    cout << ans << endl;
    return 0;
}

📝 2025年3月GESP七级真题第10题直接考查了LIS的转移方程填空，正确答案为 dp[i] = max(dp[i], dp[j] + 1)。第11题考了该程序的时间复杂度为 O(n²)。

3.3 O(n log n) 贪心+二分写法

核心思想：维护一个数组 tails，tails[k] 表示长度为 k+1 的上升子序列的最小末尾元素。对于新元素，用二分找到第一个 ≥ 它的位置并替换。

✅ 完整代码模板：LIS O(n log n)

cpp

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

const int MAXN = 100005;
int a[MAXN], tails[MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    int len = 0; // tails数组的有效长度
    for (int i = 0; i < n; i++) {
        // lower_bound找到第一个 >= a[i] 的位置（严格上升用lower_bound）
        int pos = lower_bound(tails, tails + len, a[i]) - tails;
        tails[pos] = a[i];
        if (pos == len) len++; // a[i] 比所有tail都大，子序列延长
    }
    
    cout << len << endl;
    return 0;
}

⚠️ 易错点：严格上升用 lower_bound（找第一个 ≥ a[i]）；非降（允许相等）用 upper_bound（找第一个 > a[i]）。考试选择/判断常考这个区别！

☀️ 使用 vector 的版本代码：静态数组 tails[MAXN] 无论实际 LIS 长度是多少，都会占用 100005 * 4字节 的内存。而 vector 是动态分配的，用多少占多少，且它内部维护的 size() 就是 LIS 的长度，省去了手动维护 len 变量的麻烦。

cpp

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n), tails; // tails 初始为空
    
    for (int i = 0; i < n; i++) cin >> a[i];
    
    for (int i = 0; i < n; i++) {
        // 直接在 vector 中二分查找
        auto it = lower_bound(tails.begin(), tails.end(), a[i]);
        
        if (it == tails.end()) {
            // 没找到，说明 a[i] 比所有尾巴都大，直接追加
            tails.push_back(a[i]);
        } else {
            // 找到了，替换该位置的元素
            *it = a[i];
        }
    }
    
    // tails 的实际大小就是 LIS 的长度
    cout << tails.size() << endl;
    return 0;
}

3.4 LIS考试考法速查

考法	题型	要点
填空转移方程	选择题	`dp[i] = max(dp[i], dp[j] + 1)`
时间复杂度判断	选择/判断	O(n²) 朴素版，O(n log n) 二分版
严格递增 vs 非降	判断题	`<` 和 `<=` 的区别
代码运行结果	选择题	手动模拟小规模数据

五、LCS（最长公共子序列）🔗

4.1 问题定义

给定两个序列 A 和 B，找到它们最长的公共子序列的长度。

示例：A = "ABCBDAB", B = "BDCAB"，LCS为 "BCAB"，长度为 4。

4.2 状态定义与转移

状态定义：dp[i][j] 表示 A 的前 i 个字符与 B 的前 j 个字符的 LCS 长度。

状态转移：

if A[i] == B[j]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

✅ 完整代码模板：LCS + 路径回溯

cpp

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

const int MAXN = 1005;
int dp[MAXN][MAXN];
// path[i][j] 记录转移方向: 0=左上(匹配), 1=上, 2=左
int path[MAXN][MAXN];

int main() {
    string A, B;
    cin >> A >> B;
    int n = A.size(), m = B.size();
    A = " " + A; // 下标从1开始
    B = " " + B;
    
    // DP主循环
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (A[i] == B[j]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                path[i][j] = 0; // 来自左上角
            } else if (dp[i-1][j] >= dp[i][j-1]) {
                dp[i][j] = dp[i-1][j];
                path[i][j] = 1; // 来自上方
            } else {
                dp[i][j] = dp[i][j-1];
                path[i][j] = 2; // 来自左方
            }
        }
    }
    
    cout << "LCS长度: " << dp[n][m] << endl;
    
    // 回溯求具体LCS
    string lcs = "";
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (path[i][j] == 0) {
            lcs = A[i] + lcs;
            i--; j--;
        } else if (path[i][j] == 1) {
            i--;
        } else {
            j--;
        }
    }
    cout << "LCS内容: " << lcs << endl;
    return 0;
}

💡 考试技巧：回溯路径是高频考点。记住三个方向——左上角表示字符匹配，上方表示跳过A的字符，左方表示跳过B的字符。

4.3 LCS的滚动数组优化1

LCS的 dp[i][j] 只依赖 dp[i-1][...] 和 dp[i][...]，可以用两个一维数组交替使用：

cpp

int dp[2][MAXN]; // 滚动数组
// dp[cur][j] 只依赖 dp[1-cur][j-1], dp[1-cur][j], dp[cur][j-1]

完整代码

cpp

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

const int MAXN = 1005;
// 滚动数组：只保留 2 行，交替使用
int dp[2][MAXN]; 

int main() {
    string A, B;
    cin >> A >> B;
    int n = A.size(), m = B.size();
    
    // 在字符串前加空格，让下标从 1 开始，避免边界判断
    A = " " + A;
    B = " " + B;
    
    // DP 主循环
    for (int i = 1; i <= n; i++) {
        // 核心：计算当前行 cur，上一行就是 1-cur
        int cur = i % 2;
        int prev = 1 - cur; 
        
        for (int j = 1; j <= m; j++) {
            if (A[i] == B[j]) {
                // 匹配：依赖上一行、前一列 dp[1-cur][j-1]
                dp[cur][j] = dp[prev][j - 1] + 1;
            } else {
                // 不匹配：依赖上一行同列 dp[1-cur][j] 和 当前行前一列 dp[cur][j-1]
                dp[cur][j] = max(dp[prev][j], dp[cur][j - 1]);
            }
        }
    }
    
    // 最终结果一定在最后一次计算出的那一行（即 n % 2）
    cout << "LCS长度: " << dp[n % 2][m] << endl;
    
    // ⚠️ 考场避坑提示：
    // 由于滚动数组覆盖了历史状态，这里无法像二维数组那样
    // 通过 path 数组回溯打印出具体的 LCS 字符串。
    // 如果题目要求输出具体子序列，请老老实实使用 dp[MAXN][MAXN]！
    
    return 0;
}

4.3 LCS的滚动数组优化2

普通写法：需要开一个 MAXN × MAXN 的二维数组。如果 MAXN = 10000，需要 1 亿个整型，占用约 400MB 内存，直接爆内存（MLE）。
滚动数组写法：我们观察状态转移方程：
dp[i][j] = dp[i-1][j-1] + 1 （如果匹配）
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) （如果不匹配）
你会发现，计算第 i 行的数据，仅仅只需要第 i-1 行的数据。至于第 i-2 行、第 i-3 行……算完之后就没用了，完全可以直接覆盖掉！
因此，二维数组 dp[i][j] 可以降维成一维数组 dp[j]，内存从 O(N×M)O(N×M) 骤降为 O(M) 。

但是有一个核心难点：一维滚动时怎样不覆盖上一行？

这是滚动数组最容易出错的地方。当我们用一维数组 dp[j] 来代替二维数组时：

计算当前行的 dp[j] 时，匹配分支需要 dp[i-1][j-1]（左上角），不匹配分支需要 dp[i-1][j]（上一行同列）和 dp[i][j-1]（当前行左列）。
关键矛盾：不匹配分支要的 dp[i][j-1] 是当前行已经更新过的左邻，而倒序遍历会让 dp[j-1] 仍是上一行的旧值，恰好拿不到当前行左列——于是算成了 max(上一行同列, 上一行左上角)，结果偏小（例如 A="ax"、B="xy" 会输出 0，正确应为 1）。

解决办法：一维 LCS 必须正序遍历（j 从 1 到 m），并用一个临时变量 prev 保存"左上角旧值" dp[i-1][j-1]（每次更新 dp[j] 之前先把旧 dp[j] 存进 temp 当上一行同列，再把 temp 赋给 prev 留给下一列）。这样不匹配分支才能正确取到“上一行同列”与“当前行左列”。

cpp

// 只需要一维数组，大小为 B 的长度 + 1
int dp[MAXN];

for (int i = 1; i <= n; i++) {
    int prev = 0;                 // 保存左上角旧值 dp[i-1][j-1]
    for (int j = 1; j <= m; j++) { // 必须正序遍历
        int temp = dp[j];         // 本轮更新前的 dp[j] = 上一行 dp[i-1][j]
        if (A[i] == B[j]) {
            dp[j] = prev + 1;     // 匹配：左上角 + 1
        } else {
            dp[j] = max(temp, dp[j-1]); // 不匹配：上一行同列 与 当前行左列 取大
        }
        prev = temp;              // 留给下一列当左上角
    }
}
// 最终答案依然是 dp[m]
cout << "LCS长度: " << dp[m] << endl;

💡 小贴士

“只求长度可滚动：LCS 一维必须正序遍历，并用临时变量保存左上角旧值（倒序会算错不匹配分支）；两行滚动 dp[2][m] 则可正序。若要求具体路径，乖乖用二维。”

4.4 字符串拼接的效率

代码中 lcs = A[i] + lcs; 每次都在字符串头部插入字符，这在 C++ 中会导致字符串整体后移，时间复杂度为 O(N)O(N) 。如果 LCS 极长，这会拖慢整体速度。
优化写法：在回溯时先 lcs += A[i]; 尾部追加，回溯结束后再调用 reverse(lcs.begin(), lcs.end()); 翻转，这样效率更高

六、区间DP 🎯

5.1 什么是区间DP？

区间DP 的状态是一个"区间" [l, r]，通过枚举区间内的分割点 k，将大区间拆成两个子区间合并。

核心模板：

dp[l][r] = min/max(dp[l][k] + dp[k+1][r] + 合并代价)  对所有 l ≤ k < r

5.2 枚举顺序：先长度后起点 ⚠️

🚨 高频易错点：区间DP必须先枚举区间长度，再枚举区间起点！因为大区间的答案依赖小区间，必须先算短区间再算长区间。

cpp

for (int len = 2; len <= n; len++) {       // 先枚举长度
    for (int l = 1; l + len - 1 <= n; l++) { // 再枚举起点
        int r = l + len - 1;
        for (int k = l; k < r; k++) {       // 枚举分割点
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + cost);
        }
    }
}

5.3 经典模型：石子合并

问题：n堆石子排成一行，每次合并相邻两堆，代价为两堆石子数之和，求合并为一堆的最小总代价。

状态定义：dp[l][r] 表示合并区间 [l, r] 的最小代价。

转移：dp[l][r] = min(dp[l][k] + dp[k+1][r] + sum(l,r))，其中 sum(l,r) 为区间石子总和。

✅ 完整代码模板：石子合并

cpp

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

const int MAXN = 105;
const int INF = 0x3f3f3f3f;
int a[MAXN], sum[MAXN]; // sum为前缀和
int dp[MAXN][MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i-1] + a[i]; // 前缀和
    }
    
    // 初始化
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = (i == j) ? 0 : INF;
    
    // 区间DP：先长度后起点
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            for (int k = l; k < r; k++) {
                dp[l][r] = min(dp[l][r],
                    dp[l][k] + dp[k+1][r] + sum[r] - sum[l-1]);
            }
        }
    }
    
    cout << dp[1][n] << endl;
    return 0;
}

📝 **2026年6月GESP七级编程题2"消消乐"**就是区间DP的经典应用！题目要求从数组中逐个删除元素，每次获得两侧元素之和的分数，求最大总分。核心转移方程为：
dp[l][r] = max(dp[l][k-1] + dp[k+1][r] + a[l-1] + a[r+1])
这道题直接对标HDU 5115 "Dire Wolf"，是一道标准区间DP模板题。

5.4 区间DP考试考法速查

考法	题型	要点
枚举顺序判断	选择/判断	必须先长度后起点
状态转移方程	选择题	枚举分割点k，合并左右子区间
编程实现	编程题	消消乐类问题、回文串等
时间复杂度	判断题	O(n³) 时间，O(n²) 空间

七、滚动数组优化 🔄

6.1 为什么要滚动数组？

很多DP的状态转移只依赖上一行/前一个状态，如果完整开二维数组会浪费大量空间。

优化前	优化后	适用场景
`dp[n][m]` → O(nm) 空间	`dp[2][m]` → O(m) 空间	LCS、网格DP
`dp[n][W]` → O(nW) 空间	`dp[W]` → O(W) 空间	0/1背包

⚠️ 考试技巧：int dp[5000][5000] 大约 25000000×4B ≈ 100MB，常接近或超过内存限制（128MB/256MB）。这时候必须用滚动数组！

6.2 0/1背包的滚动数组：为什么逆序遍历？

这是最高频考点之一，选择/判断/编程都可能考。

关键问题：0/1背包降为一维后，为什么内层循环要**从大到小（逆序）**遍历？

答案：因为每个物品只能选一次。如果正序遍历，dp[j-w[i]] 可能在同一轮已经被更新过了（即同一个物品被"选了两次"），变成了完全背包。逆序遍历保证 dp[j-w[i]] 用的还是**上一轮（前一个物品）**的值。

✅ 完整代码模板：0/1背包（滚动数组）

cpp

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

const int MAXW = 10005;
int dp[MAXW]; // 一维滚动数组

int main() {
    int n, W;
    cin >> n >> W;
    
    for (int i = 0; i < n; i++) {
        int w, v;
        cin >> w >> v;
        // ⚠️ 逆序遍历！保证每个物品只选一次
        for (int j = W; j >= w; j--) {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    
    cout << dp[W] << endl;
    return 0;
}

✅ 对比：完全背包（正序遍历）

cpp

// 完全背包：每个物品可选无限次
for (int i = 0; i < n; i++) {
    for (int j = w[i]; j <= W; j++) { // ✅ 正序遍历
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

🎯 考试口诀：0/1背包逆序保单选，完全背包正序允重复。

6.3 LCS的滚动数组

cpp

int dp[2][MAXN]; // 只用两行交替
int cur = 0;

for (int i = 1; i <= n; i++) {
    cur = 1 - cur; // 交替使用0和1
    for (int j = 1; j <= m; j++) {
        if (A[i] == B[j])
            dp[cur][j] = dp[1-cur][j-1] + 1;
        else
            dp[cur][j] = max(dp[1-cur][j], dp[cur][j-1]);
    }
}
// 最终答案：dp[n % 2][m]

⚠️ 易错点：滚动数组最终答案不是 dp[1][m] 或 dp[0][m]，而是 dp[n % 2][m]（取决于n的奇偶性）。

八、记忆化搜索与递推的转换 🔄

7.1 两种实现方式对比

维度	记忆化搜索（递归）	递推（迭代）
方向	自顶向下	自底向上
代码风格	类似DFS，直观	循环嵌套，紧凑
访问状态	只计算需要的状态	计算所有状态
栈溢出风险	有（递归深度大时）	无
时间复杂度	相同（都是状态数×转移复杂度）	相同

📝 2025年6月GESP七级真题判断题第9题考了"DP必须递归实现"——错误！DP可以递归（记忆化）或迭代（递推）实现。

7.2 转换示例：斐波那契数列

记忆化搜索写法

cpp

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 10005;
long long memo[MAXN]; // -1 表示未计算

long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n]; // 已计算过，直接返回
    memo[n] = fib(n-1) + fib(n-2);     // 计算并记忆
    return memo[n];
}

int main() {
    memset(memo, -1, sizeof(memo));
    int n;
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}

递推写法

cpp

long long dp[MAXN];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++)
    dp[i] = dp[i-1] + dp[i-2];

💡 转换技巧：记忆化搜索的递归参数就是DP状态，递归边界就是DP的初始条件，递归调用就是状态转移方程。

九、高频易错点汇总 ⚡

序号	易错点	正确理解
1	DP一定有多项式时间复杂度	❌ 背包问题是伪多项式复杂度
2	DP必须递归实现	❌ 递推和记忆化都可以
3	区间DP可以任意顺序枚举	❌ 必须先长度后起点
4	0/1背包逆序是为了省时间	❌ 是为了保证每个物品只选一次
5	LIS的dp[i]就是前i个元素的LIS	❌ 是以a[i]结尾的LIS
6	LCS要求子序列连续	❌ 子序列不要求连续
7	严格上升和非降用相同的二分	❌ 严格上升用lower_bound，非降用upper_bound
8	滚动数组答案在dp[0]或dp[1]	❌ 要根据最终状态判断，如dp[n%2][m]

十、📝 实战练习

练习题 1（单选题）

题目： 给定序列 [3, 1, 4, 1, 5, 9, 2, 6]，使用O(n²)的DP方法求最长严格上升子序列长度时，请问LIS的长度是多少？

A. 3
B. 4
C. 5
D. 6

🔑 点击查看答案与解析

答案： B

dp 数组最终为：

dp[0]=1, dp[1]=1, dp[2]=2, dp[3]=1, dp[4]=3, dp[5]=4, dp[6]=2, dp[7]=4

LIS 长度为 4（如 [1, 2, 5, 9] 或 [1, 2, 5, 6]）。

练习题 2（判断题）

题目： 在0/1背包问题中，将二维DP优化为一维滚动数组后，内层容量循环必须按从小到大的顺序遍历，否则无法正确计算。

🔑 点击查看答案与解析

答案： 错误 ❌

0/1背包优化为一维后，内层容量循环必须**从大到小（逆序）**遍历。如果从小到大遍历，dp[j-w[i]] 可能已经被当前物品更新过，导致同一物品被"选了多次"，变成完全背包。

练习题 3（单选题）

题目： 数组 [10, 9, 2, 5, 3, 7, 101, 18] 的最长上升子序列（LIS）长度是？（）

A. 3
B. 4
C. 5
D. 6

🔑 点击查看答案与解析

答案： B

解析： 最长上升子序列可以是 [2, 5, 7, 101] 或 [2, 3, 7, 101] 或 [2, 3, 7, 18]，长度都是 4。

验证：

2 < 5 < 7 < 101 ✓（4个元素）
2 < 3 < 7 < 101 ✓（4个元素）
2 < 3 < 7 < 18 ✓（4个元素）

选 B。

⚠️ 注意：子序列不要求连续，只要相对顺序不变就行。

---

练习题 4（判断题）

题目： 最长公共子序列（LCS）问题中，dp[i][j] 表示字符串 a 的前 i 个字符和字符串 b 的前 j 个字符的最长公共子序列的长度。（）

🔑 点击查看答案与解析

答案： 正确 ✅

解析： LCS 的标准状态定义：

dp[i][j] = a的前i个字符和 b的前j个字符的最长公共子序列长度
当 a[i-1] == b[j-1] 时：dp[i][j] = dp[i-1][j-1] + 1
当 a[i-1] != b[j-1] 时：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

答案是 dp[n][m]（n和m分别是两个字符串的长度）。

💡 为什么用 a[i-1] 和 b[j-1]？因为 dp[i][j] 表示"前i个"，而字符串下标从0开始，第i个字符的下标是 i-1。

---

练习题 5（单选题）

题目： 在一个 m×n 的网格中，从左上角走到右下角，每次只能向右或向下走一步，共有多少种走法？（用DP求解）（）

A. dp[i][j] = dp[i-1][j-1]
B. dp[i][j] = dp[i-1][j] + dp[i][j-1]
C. dp[i][j] = dp[i-1][j] × dp[i][j-1]
D. dp[i][j] = dp[i+1][j] + dp[i][j+1]

🔑 点击查看答案与解析

答案： B

解析： 走到 (i, j) 的路径数 = 从上面走下来的路径数 + 从左边走过来的路径数

即：dp[i][j] = dp[i-1][j] + dp[i][j-1]

边界条件：

第一行：只能一直向右走 → dp[0][j] = 1
第一列：只能一直向下走 → dp[i][0] = 1

选 B。

🍎 生活比喻：要到一个十字路口，要么从北边来，要么从西边来，所以走法总数 = 北边的走法 + 西边的走法。

---

练习题 6（单选题）

题目： 区间动态规划的典型枚举顺序是？（）

A. 先枚举起点，再枚举终点
B. 先枚举区间长度，再枚举起点
C. 先枚举终点，再枚举起点
D. 先枚举区间长度，再枚举终点

🔑 点击查看答案与解析

答案： B

解析： 区间 DP 的特点是：大区间的解依赖于小区间的解。

所以计算顺序必须是：

先算短的区间（长度小）
再算长的区间（长度大）

枚举方式：

cpp

for (int len = 1; len <= n; len++) {       // 先枚举区间长度
    for (int l = 0; l + len <= n; l++) {   // 再枚举起点
        int r = l + len - 1;               // 终点由长度和起点决定
        // 计算 dp[l][r]
    }
}

选 B。

💡 记忆：区间DP = 从短到长。就像搭积木，先搭小块，再拼大块。

---

练习题 7（判断题）

题目： "子序列"和"子串"是同一个概念，都要求字符连续。（）

🔑 点击查看答案与解析

答案： 错误 ❌

解析： 子序列和子串是两个不同的概念：

子串（substring）：必须连续
子序列（subsequence）：不要求连续，但相对顺序不变

例如字符串 "abcde"：

"bcd" 是子串，也是子序列 ✓
"ace" 是子序列，但不是子串 ✓（a和c之间隔了b）

🔥 高频考点：LIS（最长上升子序列）和 LCS（最长公共子序列）都是"子序列"，不是"子串"！

---

练习题 8（编程题）

题目： 给定一个长度为 n 的整数数组，求它的最长上升子序列的长度。

输入：第一行一个整数 n，第二行 n 个整数
输出：最长上升子序列的长度

样例输入：

8
10 9 2 5 3 7 101 18

样例输出：

🔑 点击查看答案与解析

答案： 参考代码（O(n²) 解法）：

cpp

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    vector<int> dp(n, 1);  // dp[i] = 以i结尾的LIS长度
    int ans = 1;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {  // 严格上升
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    
    cout << ans << endl;
    return 0;
}

解析：

定状态：dp[i] 表示以第 i 个元素结尾的最长上升子序列长度
找转移：对每个 i，检查所有 j < i，如果 a[j] < a[i]，则 dp[i] = max(dp[i], dp[j] + 1)
定初始：dp[i] = 1（每个元素自身就是长度为1的子序列）
定顺序：i 从 0 到 n-1，每个 i 检查前面所有 j

答案是 max(dp[i])，不是 dp[n-1]！

💡 时间复杂度 O(n²)，空间复杂度 O(n)。对于 n ≤ 1000 的数据完全够用。

---

十一、📊 考点总结表

考点	重要程度	出题形式	易错点
二维DP（网格路径）	⭐⭐⭐⭐⭐	选择/编程	边界初始化、转移方程
LIS 最长上升子序列	⭐⭐⭐⭐⭐	编程题/选择	答案是max(dp)不是dp[n-1]
LCS 最长公共子序列	⭐⭐⭐⭐⭐	编程题/选择	dp下标和字符串下标差1
区间DP	⭐⭐⭐⭐	选择/编程	枚举顺序：先长度后起点
滚动数组优化	⭐⭐⭐⭐	选择/判断	只能优化空间，不能优化时间
01背包一维化	⭐⭐⭐⭐⭐	选择/判断/编程	j要逆序遍历
子序列 vs 子串	⭐⭐⭐⭐	选择/判断	子序列不连续，子串连续
记忆化搜索	⭐⭐⭐	选择/判断	和递推DP等价
DP最优子结构	⭐⭐⭐⭐	选择/判断	大问题最优解包含子问题最优解
重叠子问题	⭐⭐⭐	选择/判断	子问题被反复计算，适合DP

⭐ 必背速记卡

┌─────────────────────────────────────────────┐
│      复杂动态规划 · 必背速记卡              │
├─────────────────────────────────────────────┤
│  1. DP四步：定状态、找转移、定初始、定顺序  │
│  2. LIS: dp[i]=以i结尾的LIS长度             │
│  3. LIS转移: dp[i]=max(dp[j]+1), a[j]<a[i]  │
│  4. LIS答案=max(dp[i])，不是dp[n-1]         │
│  5. LCS: dp[i][j]=a前i个和b前j个的LCS       │
│  6. LCS相等=左上+1，不等=max(上,左)         │
│  7. 网格路径: dp[i][j]=上+左                │
│  8. 子序列不连续，子串必须连续              │
│  9. 区间DP：先枚举长度，再枚举起点          │
│ 10. 滚动数组优化空间，不优化时间            │
│ 11. 01背包一维化：j逆序遍历                │
│ 12. 完全背包一维化：j顺序遍历               │
│ 13. 记忆化搜索=递归+记忆表，等价于递推DP    │
│ 14. DP两大要素：最优子结构、重叠子问题      │
│ 15. 大区间依赖小区间，区间DP从短到长        │
└─────────────────────────────────────────────┘

第3章 复杂动态规划 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

一、📋 考纲原文与考点全景图 ​

二、动态规划基础回顾 🧱 ​

1.1 DP三要素 ​

1.2 两大前提性质 ​

三、二维动态规划 📊 ​

2.1 网格路径计数/最值 ​

✅ 完整代码模板：最小路径和 ​

2.2 背包问题的二维形式 ​

四、LIS（最长上升子序列）📈 ​

3.1 问题定义 ​

3.2 O(n²) 朴素DP写法 ​

✅ 完整代码模板：LIS O(n²) ​

3.3 O(n log n) 贪心+二分写法 ​

✅ 完整代码模板：LIS O(n log n) ​

3.4 LIS考试考法速查 ​

五、LCS（最长公共子序列）🔗 ​

4.1 问题定义 ​

4.2 状态定义与转移 ​

✅ 完整代码模板：LCS + 路径回溯 ​

4.3 LCS的滚动数组优化1 ​

4.3 LCS的滚动数组优化2 ​

但是有一个核心难点：一维滚动时怎样不覆盖上一行？ ​

4.4 字符串拼接的效率 ​

六、区间DP 🎯 ​

5.1 什么是区间DP？ ​

5.2 枚举顺序：先长度后起点 ⚠️ ​

5.3 经典模型：石子合并 ​

✅ 完整代码模板：石子合并 ​

5.4 区间DP考试考法速查 ​

七、滚动数组优化 🔄 ​

6.1 为什么要滚动数组？ ​

6.2 0/1背包的滚动数组：为什么逆序遍历？ ​

✅ 完整代码模板：0/1背包（滚动数组） ​

✅ 对比：完全背包（正序遍历） ​

6.3 LCS的滚动数组 ​

八、记忆化搜索与递推的转换 🔄 ​

7.1 两种实现方式对比 ​

7.2 转换示例：斐波那契数列 ​

记忆化搜索写法 ​

递推写法 ​

九、高频易错点汇总 ⚡ ​

十、📝 实战练习 ​

练习题 1（单选题） ​

练习题 2（判断题） ​

练习题 3（单选题） ​

练习题 4（判断题） ​

练习题 5（单选题） ​

练习题 6（单选题） ​

练习题 7（判断题） ​

练习题 8（编程题） ​

十一、📊 考点总结表 ​

⭐ 必背速记卡 ​

第3章复杂动态规划

🎯 本章学习目标

🗺️ 本章知识图谱

一、📋 考纲原文与考点全景图

二、动态规划基础回顾 🧱

1.1 DP三要素

1.2 两大前提性质

三、二维动态规划 📊

2.1 网格路径计数/最值

✅ 完整代码模板：最小路径和

2.2 背包问题的二维形式

四、LIS（最长上升子序列）📈

3.1 问题定义

3.2 O(n²) 朴素DP写法

✅ 完整代码模板：LIS O(n²)

3.3 O(n log n) 贪心+二分写法

✅ 完整代码模板：LIS O(n log n)

3.4 LIS考试考法速查

五、LCS（最长公共子序列）🔗

4.1 问题定义

4.2 状态定义与转移

✅ 完整代码模板：LCS + 路径回溯

4.3 LCS的滚动数组优化1

4.3 LCS的滚动数组优化2

但是有一个核心难点：一维滚动时怎样不覆盖上一行？

4.4 字符串拼接的效率

六、区间DP 🎯

5.1 什么是区间DP？

5.2 枚举顺序：先长度后起点 ⚠️

5.3 经典模型：石子合并

✅ 完整代码模板：石子合并

5.4 区间DP考试考法速查

七、滚动数组优化 🔄

6.1 为什么要滚动数组？

6.2 0/1背包的滚动数组：为什么逆序遍历？

✅ 完整代码模板：0/1背包（滚动数组）

✅ 对比：完全背包（正序遍历）

6.3 LCS的滚动数组

八、记忆化搜索与递推的转换 🔄

7.1 两种实现方式对比

7.2 转换示例：斐波那契数列

记忆化搜索写法

递推写法

九、高频易错点汇总 ⚡

十、📝 实战练习

练习题 1（单选题）

练习题 2（判断题）

练习题 3（单选题）

练习题 4（判断题）

练习题 5（单选题）

练习题 6（单选题）

练习题 7（判断题）

练习题 8（编程题）

十一、📊 考点总结表

⭐ 必背速记卡