🧩
动态规划
10 篇文章 · 已读 0 / 10
查看专题概览 / 复习建议
共 10 题，hot 100 最难一类
核心套路
- 状态定义：
dp[i]表示”前 i 个 / 以 i 结尾”的某个量 - 转移方程：从已知子问题推当前
- 初始化 + 顺序：注意 dp[0] 含义、遍历方向
- 一维 DP → 滚动数组优化空间到 O(1)
题目列表
| 题号 | 题目 | 难度 | 状态 |
|---|---|---|---|
| 70 | 爬楼梯 | 🟢 Easy | ⬜ |
| 118 | 杨辉三角 | 🟢 Easy | ⬜ |
| 198 | 打家劫舍 | 🟡 Medium | ⬜ |
| 279 | 完全平方数 | 🟡 Medium | ⬜ |
| 322 | 零钱兑换 | 🟡 Medium | ⬜ |
| 139 | 单词拆分 | 🟡 Medium | ⬜ |
| 300 | 最长递增子序列 | 🟡 Medium | ⬜ |
| 152 | 乘积最大子数组 | 🟡 Medium | ⬜ |
| 416 | 分割等和子集 | 🟡 Medium | ⬜ |
| 32 | 最长有效括号 | 🔴 Hard | ⬜ |
易错点速查
- 198 打家劫舍：
dp[i] = max(dp[i-1], dp[i-2] + nums[i]) - 322：
dp[i] = min(dp[i-c] + 1)，初始 INT_MAX 时要判溢出 - 300：朴素 O(n²) DP；O(n log n) 用二分维护 tails 数组（不是真 LIS，是长度）
- 152：维护
maxP / minP双状态，因为负数翻转 - 416：转 0-1 背包，
dp[j] = dp[j] || dp[j - nums[i]]，j 倒序