第一章 动态规划基础理论
#
1.1 动态规划基本概念
#
- 最优子结构性质
- 重叠子问题特性
- 状态转移方程构建
- 无后效性原理
1.2 动态规划解题框架
#
- 自顶向下记忆化搜索
- 自底向上递推求解
- 状态空间设计方法
- 边界条件处理技巧
第二章 经典组合优化问题
#
2.1 背包问题系列
#
2.1.1 0-1背包问题
#
- 状态定义与转移方程
- 空间优化技巧
- 物品选择方案记录
- 完全背包问题变种
2.1.2 多重背包问题
#
- 二进制优化方法
- 单调队列优化
- 混合背包问题
- 二维费用背包
2.2 序列组合问题
#
2.2.1 最长公共子序列(LCS)
#
- 经典LCS算法
- 空间优化版本
- 多序列LCS问题
- 带权LCS变种
2.2.2 最长递增子序列(LIS)
#
- O(n²)动态规划解法
- O(nlogn)贪心优化
- 带权LIS问题
- 二维LIS扩展
2.3 划分与覆盖问题
#
2.3.1 整数划分问题
#
- 有序划分与无序划分
- 限制划分条件
- 划分数计算
- 划分方案枚举
2.3.2 集合划分问题
#
- 子集和问题
- 集合覆盖问题
- 集合划分计数
- 带权集合划分
第三章 状态压缩动态规划
#
3.1 位运算基础
#
- 常用位运算操作
- 状态压缩技巧
- 子集枚举方法
- 状态转移优化
3.2 旅行商问题(TSP)
#
- 经典TSP动态规划
- 状态压缩实现
- 哈密顿路径问题
- 带约束TSP变种
3.3 棋盘覆盖问题
#
- 多米诺骨牌覆盖
- 轮廓线动态规划
- 连通性状态压缩
- 多行状态转移
第四章 树形动态规划
#
4.1 基础树形DP
#
- 树的最大独立集
- 树的最小支配集
- 树的直径问题
- 树的重心计算
4.2 树上背包问题
#
- 依赖背包模型
- 分组背包应用
- 子树合并技巧
- 复杂度分析
4.3 换根动态规划
#
- 二次扫描法
- 父子关系转移
- 换根DP模板
- 应用场景分析
第五章 区间动态规划
#
5.1 经典区间DP问题
#
- 矩阵链乘法
- 石子合并问题
- 最优二叉搜索树
- 括号匹配问题
5.2 环形区间DP
#
- 环展开技巧
- 双倍数组方法
- 环形石子合并
- 环形能量项链
5.3 区间DP优化
#
第六章 计数与概率动态规划
#
6.1 组合计数DP
#
- 路径计数问题
- 排列计数问题
- 容斥原理应用
- 生成函数方法
6.2 期望概率DP
#
- 数学期望计算
- 概率转移方程
- 马尔可夫过程
- 随机游走问题
6.3 博弈动态规划
#
- 必胜必败状态
- SG函数理论
- Nim游戏变种
- 组合游戏分析
第七章 高级优化技巧
#
7.1 数据结构优化
#
- 线段树优化DP
- 树状数组应用
- 单调队列优化
- 平衡树维护
7.2 状态设计优化
#
7.3 算法融合优化
#
- DP与分治结合
- DP与贪心结合
- DP与网络流
- 近似算法应用
第八章 实际应用与扩展
#
8.1 工业应用场景
#
- 资源调度问题
- 生产计划优化
- 物流路径规划
- 投资组合优化
8.2 算法竞赛专题
#
- 常见题型分类
- 解题思路分析
- 代码实现技巧
- 调试与优化方法
8.3 前沿研究方向
#
- 参数化算法
- 启发式方法
- 机器学习结合
- 量子算法探索