koko PERSONAL LAB / algorithms/15-动态规划

哈希.md 双指针.md 滑动窗口.md 子串.md 普通数组.md 矩阵.md 链表.md 二叉树.md 图论.md 回溯.md 二分查找.md 栈.md 堆.md 贪心.md 动态规划.md 多维动归.md 技巧.md

$ ls algorithms/15-动态规划/

动态规划

10 篇文章 · 已读 0 / 10

01 32. 最长有效括号.md → 02 70. 爬楼梯.md → 03 118. 杨辉三角.md → 04 139. 单词拆分.md → 05 152. 乘积最大子数组.md → 06 198. 打家劫舍.md → 07 279. 完全平方数.md → 08 300. 最长递增子序列.md → 09 322. 零钱兑换.md → 10 416. 分割等和子集.md →

查看专题概览 / 复习建议

共 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 倒序

⎇ main algorithms/15-动态规划 253 notes UTF-8