动态规划入门：从斐波那契到背包问题
什么是动态规划
🎯 动态规划学习路径
1
入门
斐波那契
爬楼梯
2
基础
01背包
最长子序列
3
进阶
区间DP
树形DP
4
高级
状压DP
数位DP
动态规划（Dynamic Programming，简称DP）是信息学竞赛中最重要的算法之一。它通过把复杂问题分解成相对简单的子问题，并保存子问题的解来避免重复计算，从而高效地解决问题。
动态规划的本质
- 最优子结构：问题的最优解包含子问题的最优解
- 重叠子问题：子问题会被多次求解
- 无后效性：未来的决策不会影响已经做出的决策
动态规划vs其他算法
| 对比项 | 动态规划 | 贪心算法 | 分治算法 | 暴力枚举 |
|---|---|---|---|---|
| 时间复杂度 | 多项式级 | 线性或对数 | 对数级 | 指数级 |
| 空间复杂度 | 需要额外空间 | 常数空间 | 递归栈空间 | 较小 |
| 适用问题 | 最优化问题 | 局部最优 | 独立子问题 | 规模小 |
| 正确性 | 保证最优 | 不一定最优 | 保证正确 | 保证正确 |
从斐波那契数列开始
问题描述
斐波那契数列：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n≥2)
三种实现方法对比
方法1：暴力递归
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
// 时间复杂度：O(2^n)
// 空间复杂度：O(n)
// 问题：大量重复计算
方法2：记忆化搜索
int memo[100];
bool vis[100];
int fib(int n) {
if (n <= 1) return n;
if (vis[n]) return memo[n];
vis[n] = true;
memo[n] = fib(n-1) + fib(n-2);
return memo[n];
}
// 时间复杂度：O(n)
// 空间复杂度：O(n)
// 优点：避免重复计算
方法3：动态规划
int fib(int n) {
if (n <= 1) return n;
int dp[n+1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
// 时间复杂度：O(n)
// 空间复杂度：O(n)
方法4：空间优化
int fib(int n) {
if (n <= 1) return n;
int a = 0, b = 1, c;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)
动态规划的解题步骤
标准四步法
- 定义状态
- 确定dp数组的含义
- 明确下标表示什么
- 数组值表示什么
- 状态转移方程
- 找出状态之间的关系
- 写出递推公式
- 确保无后效性
- 初始化
- 确定边界条件
- 设置初始值
- 避免越界
- 计算顺序
- 确定遍历方向
- 保证依赖关系
- 返回目标值
经典问题1：爬楼梯
题目描述
你正在爬楼梯，需要n阶才能到达楼顶。每次可以爬1或2个台阶，有多少种不同的方法可以爬到楼顶？
解题思路
- 状态定义：dp[i]表示爬到第i阶的方法数
- 转移方程：dp[i] = dp[i-1] + dp[i-2]
- 初始化：dp[0]=1, dp[1]=1
代码实现
int climbStairs(int n) {
if (n <= 2) return n;
vector<int> dp(n + 1);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
变式问题
| 变式 | 描述 | 转移方程 |
|---|---|---|
| 一次可爬1-3阶 | 每次可以爬1、2或3阶 | dp[i]=dp[i-1]+dp[i-2]+dp[i-3] |
| 有代价爬楼梯 | 每阶有不同代价 | dp[i]=min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]) |
| 不能连续爬2阶 | 限制条件 | 需要二维状态 |
经典问题2：最长上升子序列（LIS）
题目描述
给定数组nums，找到最长严格递增子序列的长度。
方法1：动态规划 O(n²)
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1); // dp[i]表示以nums[i]结尾的LIS长度
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
方法2：二分优化 O(nlogn)
int lengthOfLIS(vector<int>& nums) {
vector<int> tails; // tails[i]表示长度为i+1的LIS的最小尾元素
for (int num : nums) {
auto it = lower_bound(tails.begin(), tails.end(), num);
if (it == tails.end()) {
tails.push_back(num);
} else {
*it = num;
}
}
return tails.size();
}
经典问题3：0-1背包问题
问题描述
有n个物品，第i个物品重量为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])
二维DP实现
int knapsack01(int n, int W, vector<int>& w, vector<int>& v) {
vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= W; j++) {
dp[i][j] = dp[i-1][j]; // 不选第i个物品
if (j >= w[i]) {
dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
}
}
}
return dp[n][W];
}
一维优化（滚动数组）
int knapsack01(int n, int W, vector<int>& w, vector<int>& v) {
vector<int> dp(W+1, 0);
for (int i = 1; i <= n; i++) {
for (int j = W; j >= w[i]; j--) { // 注意：逆序遍历
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}
return dp[W];
}
背包问题家族
各类背包问题对比
| 类型 | 特点 | 转移方程 | 遍历顺序 |
|---|---|---|---|
| 0-1背包 | 每个物品只能选一次 | dp[j]=max(dp[j],dp[j-w]+v) | 逆序 |
| 完全背包 | 每个物品可选无限次 | dp[j]=max(dp[j],dp[j-w]+v) | 正序 |
| 多重背包 | 每个物品有限个 | 需要拆分或二进制优化 | 逆序 |
| 分组背包 | 物品分组，每组选一个 | 三重循环 | 逆序 |
完全背包代码
int completeKnapsack(int n, int W, vector<int>& w, vector<int>& v) {
vector<int> dp(W+1, 0);
for (int i = 1; i <= n; i++) {
for (int j = w[i]; j <= W; j++) { // 正序遍历
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}
return dp[W];
}
区间DP
石子合并问题
n堆石子排成一排，每次只能合并相邻两堆，代价为两堆石子数量之和，求最小代价。
int stoneGame(vector<int>& stones) {
int n = stones.size();
vector<int> sum(n+1, 0); // 前缀和
for (int i = 0; i < n; i++) {
sum[i+1] = sum[i] + stones[i];
}
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int len = 2; len <= n; len++) { // 区间长度
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
for (int k = i; k < j; k++) {
dp[i][j] = min(dp[i][j],
dp[i][k] + dp[k+1][j] + sum[j+1] - sum[i]);
}
}
}
return dp[0][n-1];
}
状态压缩DP
旅行商问题（TSP）
给定n个城市的距离矩阵，从0号城市出发，访问所有城市恰好一次后回到起点，求最短路径。
int tsp(vector<vector<int>>& dist) {
int n = dist.size();
int ALL = (1 << n) - 1;
vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX/2));
dp[1][0] = 0; // 从0出发
for (int mask = 1; mask <= ALL; mask++) {
for (int i = 0; i < n; i++) {
if (!(mask & (1 << i))) continue;
for (int j = 0; j < n; j++) {
if (i == j || !(mask & (1 << j))) continue;
dp[mask][i] = min(dp[mask][i],
dp[mask^(1<<i)][j] + dist[j][i]);
}
}
}
int ans = INT_MAX;
for (int i = 1; i < n; i++) {
ans = min(ans, dp[ALL][i] + dist[i][0]);
}
return ans;
}
DP优化技巧
1. 滚动数组优化
当dp[i]只依赖dp[i-1]时，可以用两个数组交替使用：
vector<int> prev(m), curr(m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
curr[j] = /* 根据prev计算 */;
}
swap(prev, curr);
}
2. 斜率优化
适用于形如：dp[i] = min{dp[j] + cost(j, i)}的转移方程
3. 单调队列优化
当转移有区间限制时，维护单调队列降低复杂度
4. 四边形不等式优化
适用于区间DP的优化
学习建议与练习题推荐
学习路线
- 入门阶段
- 斐波那契、爬楼梯
- 简单线性DP
- 练习20-30题
- 基础阶段
- 背包问题全家族
- LIS、LCS问题
- 练习50题
- 进阶阶段
- 区间DP
- 树形DP
- 状态压缩DP
- 高级阶段
- 数位DP
- 概率DP
- DP优化技巧
经典练习题
| 难度 | 题目 | 知识点 |
|---|---|---|
| 简单 | 最大子数组和 | 线性DP |
| 简单 | 打家劫舍 | 线性DP |
| 中等 | 最长公共子序列 | 二维DP |
| 中等 | 编辑距离 | 二维DP |
| 中等 | 零钱兑换 | 完全背包 |
| 困难 | 正则表达式匹配 | 字符串DP |
| 困难 | 戳气球 | 区间DP |
总结
动态规划是信息学竞赛的核心算法，掌握好DP对提升竞赛水平至关重要。学习DP的关键点：
- 理解本质：最优子结构和重叠子问题
- 掌握方法：状态定义、转移方程、初始化、计算顺序
- 大量练习：从简单到复杂，循序渐进
- 总结归纳：形成自己的DP模板库
- 灵活应用：识别问题类型，选择合适方法
记住，DP不是背公式，而是一种思维方式。通过不断练习和思考，你一定能掌握这个强大的算法工具！
Views: 0
答复