第6次内容

1.上次内容-动态规划

1.1 动态规划定义

动态规划（Dynamic Programming） 是一种通过分解重叠子问题、存储子解以避免重复计算，从而高效求解最优化问题的算法思想。

本质：记忆化 + 子问题分解

1.2 适用条件（三要素）

条件	说明	本题体现
最优子结构	原问题最优解包含子问题最优解	全局最大和 = 所有 dp[i] 的最大值
重叠子问题	子问题被多次重复计算	dp[i] 依赖 dp[i-1]，存在递推关系
无后效性	当前状态与历史路径无关	dp[i] 仅由 dp[i-1] 和 nums[i] 决定

1.3 核心要素（DP 四步法）

1. 状态定义
   dp[i] = 以 nums[i] 结尾的最大子数组和

2. 状态转移方程
   dp[i] = max(nums[i], dp[i-1] + nums[i])

3. 边界条件
   dp[0] = nums[0]

4. 计算顺序
   自底向上（从左到右迭代）

1.4 解题步骤模板

1. 问题分析：是否满足 DP 三条件？求最大/最小/方案数？
2. 状态定义：明确 dp 含义（如“以 i 结尾”）
3. 转移方程：列出所有决策选项，写出递推式
4. 边界初始化：处理最小规模问题（如 i=0）
5. 实现与优化：迭代实现，考虑空间压缩
6. 结果提取：从 dp 数组或变量中获取答案

1.5 优化技巧

• 空间优化：若状态仅依赖前一项，可用滚动变量（O(1) 空间）
• 状态压缩：用位掩码等技巧减少状态维度（适用于状态数少的问题）
• 斜率优化：针对特定转移形式进一步优化时间（进阶）

1.6 DP 问题分类

类型	典型问题
线性 DP	最大子数组和、最长递增子序列、背包问题
区间 DP	矩阵连乘、石子合并
树形 DP	树上最大独立集、树的直径
状态压缩 DP	旅行商问题（TSP）、铺砖问题

---

2.本次内容-真题

(1) 买包子

(2) 买不到的数字

(3) 买卖股票的最佳时机I

3.本次内容总结

3.1 动态规划解题步骤

见 1.4

3.2 常见误区

• 误解最优子结构：未理解原问题如何分解为子问题。
• 忽略重叠性：未发现重复计算导致效率低下。
• 错误的状态转移：转移公式写错或逻辑有误。
• 边界不清：初始条件和边界值设置不当。

3.3 学习建议

• 多做经典题目练手，如最长递增子序列、背包问题等。
• 学会分析问题的最优子结构和重叠子问题特性。
• 掌握不同类型 DP 的特点和适用场景