{< katex />}
第一章 动态规划基础理论 #
1.1 动态规划概述 #
- 动态规划的定义与起源
- 动态规划的基本思想
- 动态规划与分治法的区别
- 动态规划的适用场景
1.2 动态规划基本要素 #
- 最优子结构性质
- 重叠子问题性质
- 状态转移方程
- 边界条件
1.3 动态规划求解步骤 #
- 问题分析阶段
- 状态定义方法
- 状态转移方程建立
- 初始条件确定
- 计算顺序选择
- 最优解构造
第二章 经典动态规划问题 #
2.1 线性动态规划 #
- 最长递增子序列(LIS)
- 最长公共子序列(LCS)
- 最大子数组和
- 编辑距离问题
2.2 背包问题系列 #
- 0-1背包问题
- 完全背包问题
- 多重背包问题
- 分组背包问题
- 二维费用背包问题
2.3 区间动态规划 #
- 矩阵连乘问题
- 石子合并问题
- 最优二叉搜索树
- 多边形三角剖分
2.4 树形动态规划 #
- 树的最大独立集
- 树的最小支配集
- 树的最小点覆盖
- 树的重心与直径
第三章 动态规划优化技术 #
3.1 空间优化方法 #
- 滚动数组技术
- 状态压缩技巧
- 降维优化策略
3.2 时间复杂度优化 #
- 单调队列优化
- 斜率优化
- 四边形不等式优化
- 决策单调性优化
3.3 数据结构辅助优化 #
- 线段树优化
- 树状数组优化
- 堆优化方法
- 并查集辅助
第四章 动态规划状态设计 #
4.1 状态表示方法 #
- 一维状态设计
- 二维状态设计
- 高维状态设计
- 状态压缩表示
4.2 状态转移技巧 #
- 前向转移与后向转移
- 多决策状态转移
- 概率状态转移
- 带约束状态转移
4.3 状态空间分析 #
- 状态空间复杂度分析
- 状态冗余消除
- 状态等价类划分
- 状态剪枝策略
第五章 动态规划应用领域 #
5.1 组合优化问题 #
- 旅行商问题(TSP)
- 调度问题
- 资源分配问题
- 网络流问题
5.2 序列处理问题 #
- 字符串匹配与处理
- 序列比对问题
- 语音识别应用
- 生物信息学应用
5.3 图论问题 #
- 最短路径问题
- 最大流问题
- 最小生成树问题
- 图着色问题
5.4 游戏与博弈 #
- 取石子游戏
- 棋盘游戏
- 博弈树搜索
- 强化学习应用
第六章 动态规划算法实现 #
6.1 记忆化搜索 #
- 递归实现方法
- 记忆化技术
- 递归与迭代对比
- 实现注意事项
6.2 迭代实现 #
- 自底向上实现
- 循环顺序选择
- 状态更新策略
- 代码模板设计
6.3 编程语言实现 #
- C++实现技巧
- Python实现方法
- Java实现特点
- 函数式编程实现
第七章 动态规划扩展与变体 #
7.1 概率动态规划 #
- 马尔可夫决策过程
- 期望值计算
- 随机环境下的DP
- 风险敏感DP
7.2 多目标动态规划 #
- Pareto最优解
- 权重和方法
- 约束方法
- 多目标状态设计
7.3 近似动态规划 #
- 值函数近似
- 策略迭代近似
- 神经网络应用
- 强化学习结合
第八章 动态规划实战训练 #
8.1 竞赛题目解析 #
- ACM/ICPC经典题目
- LeetCode高频题目
- Codeforces典型题目
- 面试常见题目
8.2 实际问题建模 #
- 实际问题转化为DP模型
- 状态设计的实践经验
- 边界条件处理技巧
- 调试与验证方法
8.3 性能分析与调优 #
- 时间复杂度分析
- 空间复杂度分析
- 常数优化技巧
- 测试用例设计