第一章 线性动态规划基础概念 #

1.1 动态规划基本思想 #

• 最优子结构原理
• 重叠子问题特性
• 状态转移方程构建
• 记忆化搜索与自底向上方法

1.2 线性动态规划特征 #

• 线性结构问题定义
• 单序列与双序列问题
• 线性状态转移模式
• 时间复杂度分析

1.3 基本解题框架 #

• 状态定义方法
• 状态转移方程设计
• 边界条件处理
• 结果提取与优化

第二章 一维线性动态规划 #

2.1 经典一维DP问题 #

• 斐波那契数列问题
• 爬楼梯问题变种
• 最大子数组和问题
• 打家劫舍系列问题

2.2 状态设计与优化 #

• 单一状态变量设计
• 多状态变量设计
• 空间复杂度优化技巧
• 滚动数组应用

2.3 一维DP扩展应用 #

• 股票买卖问题
• 跳跃游戏问题
• 等差数列划分
• 乘积最大子数组

第三章 二维线性动态规划 #

3.1 双序列匹配问题 #

• 最长公共子序列(LCS)
• 编辑距离问题
• 最长递增子序列(LIS)
• 字符串匹配问题

3.2 矩阵路径问题 #

• 最小路径和
• 不同路径计数
• 三角形最小路径和
• 带障碍物的路径问题

3.3 区间动态规划 #

• 矩阵链乘法
• 石子合并问题
• 括号匹配问题
• 最优二叉搜索树

第四章 线性DP优化技巧 #

4.1 时间复杂度优化 #

• 单调队列优化
• 斜率优化
• 四边形不等式优化
• 决策单调性优化

4.2 空间复杂度优化 #

• 滚动数组技术
• 状态压缩技巧
• 降维处理方法
• 内存优化策略

4.3 预处理与后处理 #

• 前缀和与差分数组
• 后缀数组预处理
• 结果重构方法
• 多解输出技巧

第五章 线性DP变种与扩展 #

5.1 带约束的线性DP #

• 背包问题变种
• 资源分配问题
• 容量限制问题
• 多约束条件处理

5.2 概率与期望DP #

• 概率动态规划基础
• 期望值计算
• 马尔可夫决策过程
• 随机游走问题

5.3 计数与组合DP #

• 组合数计算
• 排列计数问题
• 划分计数问题
• 生成函数应用

第六章 线性DP实战应用 #

6.1 字符串处理应用 #

• 回文子串问题
• 正则表达式匹配
• 文本对齐问题
• DNA序列比对

6.2 数值计算应用 #

• 整数拆分问题
• 完全平方数问题
• 零钱兑换问题
• 数字三角形问题

6.3 图论中的线性DP #

• DAG上的动态规划
• 树形DP基础
• 最短路径变种
• 网络流相关问题

第七章 线性DP算法实现 #

7.1 编程语言实现 #

• C++实现模板
• Python实现技巧
• Java实现要点
• 递归与迭代实现对比

7.2 调试与测试 #

• 状态转移验证
• 边界条件测试
• 性能分析方法
• 常见错误排查

7.3 竞赛应用技巧 #

• 时间复杂度估算
• 空间复杂度控制
• 输入输出优化
• 代码模板积累

第八章 线性DP进阶专题 #

8.1 多维状态设计 #

• 高维状态压缩
• 状态合并技巧
• 状态转移简化
• 复杂约束处理

8.2 动态规划与贪心 #

• 贪心选择性质
• 动态规划贪心结合
• 最优性证明
• 适用范围分析

8.3 线性DP与其他算法 #

• 分治策略结合
• 搜索算法融合
• 数学方法应用
• 机器学习中的DP