第一章 动态规划基础理论 #
1.1 动态规划基本概念 #
- 最优子结构原理
- 重叠子问题特性
- 状态转移方程构建
- 记忆化与制表法
1.2 动态规划解题框架 #
- 状态定义方法
- 状态转移设计
- 边界条件处理
- 结果提取策略
第二章 线性序列DP问题 #
2.1 最长递增子序列(LIS) #
- 经典O(n²)解法
- 贪心+二分O(nlogn)优化
- 最长非递减子序列变体
- 带权LIS问题
2.2 最长公共子序列(LCS) #
- 标准LCS算法
- 空间优化技巧
- 多序列LCS问题
- LCS应用场景
2.3 最大子数组和 #
- Kadane算法原理
- 环形数组最大和
- 二维矩阵最大子矩阵和
- 带长度限制的最大子数组和
第三章 区间序列DP问题 #
3.1 矩阵链乘法 #
- 最优括号化问题
- 区间DP状态设计
- 最优解重构方法
- 实际应用案例
3.2 石子合并问题 #
- 线性石子合并
- 环形石子合并
- 最小代价与最大代价
- 四边形不等式优化
3.3 括号匹配问题 #
- 最长有效括号子串
- 括号序列合法性判断
- 生成所有有效括号组合
- 带权括号匹配
第四章 字符串序列DP问题 #
4.1 编辑距离 #
- Levenshtein距离计算
- 操作代价自定义
- 应用：拼写检查
- 应用：DNA序列比对
4.2 正则表达式匹配 #
- 通配符匹配问题
- 正则表达式引擎实现
- 回溯与DP结合
- 性能优化技巧
4.3 回文子序列 #
- 最长回文子序列
- 回文子串计数
- 分割回文串
- 回文分割最小次数
第五章 背包序列DP问题 #
5.1 0-1背包问题 #
- 基础0-1背包
- 空间优化技巧
- 恰好装满问题
- 方案计数问题
5.2 完全背包问题 #
- 物品无限取用
- 状态转移优化
- 组合与排列区别
- 多重背包问题
5.3 分组背包问题 #
- 物品分组约束
- 依赖背包问题
- 树形依赖背包
- 二维费用背包
第六章 状态压缩DP #
6.1 位运算基础 #
- 常用位操作技巧
- 状态表示方法
- 状态转移实现
- 复杂度分析
6.2 旅行商问题(TSP) #
- 经典TSP解法
- 状态压缩实现
- 哈密顿路径问题
- 实际应用优化
6.3 棋盘覆盖问题 #
- 多米诺骨牌覆盖
- 轮廓线DP技术
- 连通性状态表示
- 插头DP简介
第七章 树形序列DP问题 #
7.1 树形DP基础 #
- 子树问题处理
- 树上背包问题
- 直径与重心计算
- 换根DP技术
7.2 二叉树DP问题 #
- 二叉搜索树计数
- 最优二叉搜索树
- 二叉树最大路径和
- 二叉树染色问题
第八章 序列分割与划分 #
8.1 序列分割问题 #
- 最小分割代价
- 最大分割收益
- 带约束分割问题
- 分割方案计数
8.2 整数划分问题 #
- 划分数计算
- 不同划分方式
- 带限制划分
- 生成函数应用
第九章 概率与期望DP #
9.1 概率DP基础 #
- 期望线性性质
- 马尔可夫过程
- 状态转移概率
- 终止条件处理
9.2 博弈论DP #
- 必胜必败状态
- Nim游戏变体
- 公平博弈分析
- SG函数应用
第十章 高级优化技巧 #
10.1 单调队列优化 #
- 滑动窗口最值
- 决策单调性
- 应用：限制长度LIS
- 应用：带限制子数组和
10.2 斜率优化 #
- 凸壳维护技术
- 决策点筛选
- 应用：任务调度
- 应用：资源分配
10.3 四边形不等式 #
- 区间包含单调性
- 四边形不等式性质
- 决策单调性证明
- 实际应用案例
第十一章 实际应用场景 #
11.1 生物信息学应用 #
- DNA序列比对
- 蛋白质结构预测
- 基因识别问题
- 进化树构建
11.2 自然语言处理 #
- 机器翻译对齐
- 文本相似度计算
- 命名实体识别
- 句法分析应用
11.3 金融与经济 #
- 股票交易问题
- 投资组合优化
- 风险管理模型
- 资源调度问题