【数据结构与算法】第47篇：算法思想（二）：动态规划（DP）

目录一、什么是动态规划1.1 DP的适用条件1.2 DP的两种实现方式1.3 演变路径二、经典问题一0-1背包2.1 问题描述2.2 状态定义与转移方程2.3 二维DP实现2.4 空间优化一维DP三、经典问题二最长公共子序列LCS3.1 问题描述3.2 状态定义与转移方程3.3 代码实现四、DP问题解题模板4.1 解题步骤4.2 常见DP类型五、常见DP优化技巧六、复杂度分析七、DP vs 贪心 vs 分治八、小结九、思考题一、什么是动态规划1.1 DP的适用条件条件说明最优子结构大问题的最优解包含子问题的最优解重叠子问题子问题被重复计算多次1.2 DP的两种实现方式方式方向特点自顶向下记忆化搜索递归 缓存容易思考可能有栈溢出风险自底向上递推迭代效率高是标准的DP写法1.3 演变路径text暴力递归 → 记忆化搜索递归缓存 → 动态规划递推我们以斐波那契数列为例展示这个演变c// 版本1暴力递归 O(2^n) int fib1(int n) { if (n 1) return n; return fib1(n-1) fib1(n-2); } // 版本2记忆化搜索 O(n) int memo[100]; int fib2(int n) { if (n 1) return n; if (memo[n] ! 0) return memo[n]; memo[n] fib2(n-1) fib2(n-2); return memo[n]; } // 版本3动态规划递推 O(n) int fib3(int n) { if (n 1) return n; int dp[n1]; dp[0] 0; dp[1] 1; for (int i 2; i n; i) { dp[i] dp[i-1] dp[i-2]; } return dp[n]; }二、经典问题一0-1背包2.1 问题描述有 n 个物品第 i 个物品重量为w[i]价值为v[i]。给定一个容量为 W 的背包每个物品只能选一次0或1求能装入的最大总价值。2.2 状态定义与转移方程状态定义dp[i][j]表示前 i 个物品背包容量为 j 时的最大价值状态转移对于第 i 个物品下标从1开始text不选第 i 个物品dp[i][j] dp[i-1][j] 选第 i 个物品dp[i][j] dp[i-1][j - w[i]] v[i] 需要 j ≥ w[i] 取最大值dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])初始化dp[0][j] 0没有物品时价值为02.3 二维DP实现c#include stdio.h #include string.h #define MAX_N 100 #define MAX_W 1000 int max(int a, int b) { return a b ? a : b; } int knapsack2D(int w[], int v[], int n, int capacity) { int dp[MAX_N][MAX_W] {0}; for (int i 1; i n; i) { for (int j 0; j capacity; j) { // 不选第 i 个物品 dp[i][j] dp[i-1][j]; // 选第 i 个物品如果装得下 if (j w[i-1]) { dp[i][j] max(dp[i][j], dp[i-1][j - w[i-1]] v[i-1]); } } } return dp[n][capacity]; } int main() { int w[] {2, 3, 4, 5}; int v[] {3, 4, 5, 6}; int n 4; int capacity 8; int result knapsack2D(w, v, n, capacity); printf(0-1背包最大价值: %d\n, result); return 0; }运行结果text0-1背包最大价值: 102.4 空间优化一维DP观察转移方程dp[i][j]只依赖dp[i-1][...]可以压缩成一维数组。注意内层循环必须从大到小遍历防止同一物品被多次使用。cint knapsack1D(int w[], int v[], int n, int capacity) { int dp[MAX_W] {0}; for (int i 0; i n; i) { for (int j capacity; j w[i]; j--) { // 从大到小 dp[j] max(dp[j], dp[j - w[i]] v[i]); } } return dp[capacity]; }三、经典问题二最长公共子序列LCS3.1 问题描述给定两个字符串text1和text2求它们的最长公共子序列的长度。子序列不要求连续但顺序不能改变。示例text1 abcde, text2 ace → LCS ace (长度3)text1 abc, text2 abc → LCS abc (长度3)text1 abc, text2 def → LCS (长度0)3.2 状态定义与转移方程状态定义dp[i][j]表示text1[0..i-1]和text2[0..j-1]的LCS长度状态转移text如果 text1[i-1] text2[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为03.3 代码实现c#include stdio.h #include string.h #define MAX 1000 int max(int a, int b) { return a b ? a : b; } int longestCommonSubsequence(char *text1, char *text2) { int len1 strlen(text1); int len2 strlen(text2); int dp[MAX][MAX] {0}; for (int i 1; i len1; i) { for (int j 1; j len2; j) { if (text1[i-1] text2[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[len1][len2]; } // 打印LCS字符串可选 void printLCS(char *text1, char *text2) { int len1 strlen(text1); int len2 strlen(text2); int dp[MAX][MAX] {0}; // 先填表 for (int i 1; i len1; i) { for (int j 1; j len2; j) { if (text1[i-1] text2[j-1]) { dp[i][j] dp[i-1][j-1] 1; } else { dp[i][j] max(dp[i-1][j], dp[i][j-1]); } } } // 回溯打印 int i len1, j len2; char lcs[MAX]; int index dp[len1][len2]; lcs[index] \0; while (i 0 j 0) { if (text1[i-1] text2[j-1]) { lcs[--index] text1[i-1]; i--; j--; } else if (dp[i-1][j] dp[i][j-1]) { i--; } else { j--; } } printf(LCS: %s\n, lcs); } int main() { char text1[] abcde; char text2[] ace; int len longestCommonSubsequence(text1, text2); printf(最长公共子序列长度: %d\n, len); printLCS(text1, text2); return 0; }运行结果text最长公共子序列长度: 3 LCS: ace四、DP问题解题模板4.1 解题步骤步骤说明1. 定义状态确定dp[i]或dp[i][j]的含义2. 找状态转移推导dp[i]与子问题的关系3. 初始化确定边界条件4. 确定遍历顺序保证子问题先计算5. 优化可选空间压缩4.2 常见DP类型类型典型问题状态定义线性DP最长上升子序列dp[i] 以 i 结尾的LIS区间DP石子合并dp[i][j] 区间[i,j]的最优解背包DP0-1背包、完全背包dp[j] 容量j的最大价值序列DPLCS、编辑距离dp[i][j] 两个前缀的匹配状态压缩DP旅行商问题dp[mask][i] 用二进制表示状态五、常见DP优化技巧优化说明示例空间压缩滚动数组降维0-1背包一维数组状态压缩用位运算表示状态旅行商问题单调队列滑动窗口优化滑动窗口最大值斜率优化决策单调性任务调度四边形不等式区间DP优化石子合并六、复杂度分析问题时间复杂度空间复杂度优化后空间斐波那契O(n)O(n)O(1)0-1背包O(n × W)O(n × W)O(W)LCSO(m × n)O(m × n)O(min(m,n))最长上升子序列O(n²) / O(n log n)O(n)O(n)七、DP vs 贪心 vs 分治算法子问题重叠最优子结构典型问题分治不重叠有归并排序贪心不适用有贪心选择性质活动选择动态规划重叠有背包、LCS八、小结这一篇我们学习了动态规划的核心思想要点说明演变路径暴力递归 → 记忆化搜索 → 动态规划0-1背包dp[j] max(dp[j], dp[j-w[i]] v[i])内层倒序LCSdp[i][j] dp[i-1][j-1] 1或max(dp[i-1][j], dp[i][j-1])解题步骤定义状态 → 转移方程 → 初始化 → 遍历顺序DP的核心找到正确的状态定义和状态转移方程剩下的就是填表。下一篇我们讲贪心算法。九、思考题0-1背包的一维优化中为什么内层循环要从大到小如果从小到大会怎样最长公共子序列中如何打印出所有LCS不唯一时如何用DP解决“最长上升子序列”问题时间复杂度分别是O(n²)和O(n log n)编辑距离Levenshtein Distance的状态转移方程是什么尝试实现。欢迎在评论区讨论你的答案。