动态规划概述
什么是动态规划
【动态规划】(Dynamic Programming, DP)是一种通过将复杂问题分解为更简单的子问题来解决的算法思想。它适用于有重叠子问题和最优子结构性质的问题，通过存储子问题的解来避免重复计算，从而提高效率。
动态规划的核心思想
- 问题分解：将原问题分解为结构相似的子问题
- 状态定义：确定问题的状态表示，即定义DP[i]或DP[i][j]等的具体含义
- 递推方程：建立状态之间的转移关系，使用数学表达式形如DP[i] = f(DP[i-1], DP[i-2], ...)
- 边界条件：确定初始状态的值，例如DP[0] = 0, DP[1] = 1等
- 计算顺序：按照依赖关系组织计算顺序，通常是自底向上
适用条件
动态规划适用于满足以下两个条件的问题：
- 最优子结构：问题的最优解包含子问题的最优解，即可以通过组合子问题的最优解得到原问题的最优解
- 重叠子问题：在求解过程中，相同的子问题会被重复计算，通过存储中间结果可以避免重复计算
动态规划的实现方式
自顶向下(记忆化搜索)：
- 从原问题出发，递归求解子问题
- 使用记忆化技术存储已解决的子问题结果
- 优点：实现直观，容易理解
- 缺点：有函数调用开销，可能导致栈溢出
自底向上(递推)：
- 从最小的子问题开始，逐步构建更大的子问题解
- 通常使用数组存储中间结果
- 优点：效率更高，没有递归开销
- 缺点：实现可能不够直观
动态规划的步骤
定义状态：
- 明确状态的含义
- 状态需要包含足够的信息，以决定子问题的解
确定状态转移方程：
- 找出状态之间的关系
- 确定如何从已知状态推导出未知状态
确定边界条件和初始状态：
- 设置最基本子问题的解
- 确保所有状态都能从初始状态推导出来
确定计算顺序：
- 通常按照状态的依赖关系来安排计算顺序
- 确保计算某个状态时，它依赖的所有状态都已计算出来
优化空间（可选）：
- 分析状态的依赖关系，减少存储空间
- 常见优化：滚动数组、状态压缩等
常见动态规划类型
线性DP：状态按照一维进行推导
- 例：最长递增子序列、编辑距离
区间DP：状态定义在区间上
- 例：最长回文子串、石子合并
背包DP：物品选择和容量约束问题
- 例：0-1背包、完全背包、多重背包
状态压缩DP：使用二进制表示状态的DP
- 例：旅行商问题、集合覆盖问题
树形DP：在树结构上进行动态规划
- 例：树的最大独立集、树的直径
数位DP：按照数字位进行计算的DP
- 例：计算特定范围内满足条件的数字个数
优化技巧
空间优化：
- 滚动数组：当状态只依赖于前面有限个状态时
- 状态压缩：使用位运算表示状态
- 内存复用：重复利用数组空间
预处理：
- 提前计算常用值
- 构建辅助数据结构
决策单调性：
- 利用问题的单调性质优化状态转移
- 例如：斜率优化、四边形不等式优化
分治优化：
- 将DP与分治结合
- 适用于具有特殊结构的问题
典型例题分析
例题1：最长递增子序列(LIS)
// 动态规划解法，时间复杂度O(n^2)
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
// dp[i]表示以nums[i]结尾的最长递增子序列的长度
vector<int> dp(n, 1);
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxLen = max(maxLen, dp[i]);
}
return maxLen;
}
// 优化解法，使用二分查找，时间复杂度O(nlogn)
int lengthOfLIS_optimized(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
// tails[i]表示长度为i+1的递增子序列的末尾元素的最小值
vector<int> tails(n, 0);
int len = 0;
for (int num : nums) {
// 二分查找，找到第一个大于等于num的位置
int left = 0, right = len;
while (left < right) {
int mid = left + (right - left) / 2;
if (tails[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
tails[left] = num;
if (left == len) len++;
}
return len;
}
例题2：0-1背包问题
// 0-1背包问题，二维DP数组实现
int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
int n = weights.size();
// dp[i][j]表示前i个物品，背包容量为j时的最大价值
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= capacity; j++) {
if (weights[i-1] <= j) {
// 选择第i个物品或不选
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);
} else {
// 不能选择第i个物品
dp[i][j] = dp[i-1][j];
}
}
}
return dp[n][capacity];
}
// 0-1背包问题，一维DP数组优化实现
int knapsack_optimized(vector<int>& weights, vector<int>& values, int capacity) {
int n = weights.size();
// dp[j]表示背包容量为j时的最大价值
vector<int> dp(capacity + 1, 0);
for (int i = 0; i < n; i++) {
// 必须逆序遍历，防止物品被重复使用
for (int j = capacity; j >= weights[i]; j--) {
dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[capacity];
}
例题3：编辑距离
// 编辑距离问题
int minDistance(string word1, string word2) {
int m = word1.length();
int n = word2.length();
// dp[i][j]表示word1前i个字符转换到word2前j个字符需要的最少操作数
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// 边界条件
for (int i = 0; i <= m; i++) {
dp[i][0] = i; // 删除word1的i个字符
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j; // 插入j个字符到word1
}
// 状态转移
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i-1] == word2[j-1]) {
dp[i][j] = dp[i-1][j-1]; // 无需操作
} else {
dp[i][j] = min(dp[i-1][j-1], // 替换操作
min(dp[i-1][j], // 删除操作
dp[i][j-1])); // 插入操作
dp[i][j] += 1; // 操作数+1
}
}
}
return dp[m][n];
}
常见错误和注意事项
状态定义不清晰：
- 确保状态能够唯一表示子问题
- 状态包含足够的信息
边界条件处理不当：
- 仔细分析初始情况
- 处理特殊输入，如空序列
状态转移方程不正确：
- 考虑所有可能的转移路径
- 确保递推关系的正确性
计算顺序错误：
- 确保计算某状态时，其依赖的状态已计算
- 注意数组的遍历顺序
溢出问题：
- 注意大数运算可能的溢出
- 必要时采用适当的取模操作
优化过度导致错误：
- 在优化空间前确保基本算法正确
- 空间优化后仔细检查依赖关系
练习题推荐
线性DP：
区间DP：
背包问题：
状态压缩DP：
树形DP：
总结
动态规划是解决优化问题的强大工具，尤其适合具有重叠子问题和最优子结构的问题。掌握动态规划需要理解其核心思想，并通过大量练习培养解决问题的直觉。在实践中，合理定义状态、推导转移方程、处理边界条件是成功应用动态规划的关键步骤。
随着经验的积累，你将能够更快地识别适合动态规划的问题，并设计出高效的解决方案。在接下来的章节中，我们将更详细地探讨各种类型的动态规划问题及其应用场景。