一、上期回顾掌握回溯 DFS子集、组合、全排列、回溯模板、剪枝去重解决暴力枚举类搜索题。今天进入算法天花板模块动态规划 DP从最简单入门题开始建立 DP 思维。二、动态规划核心思想大事化小把大问题拆成多个相同的小问题保存历史结果用数组 dp 记录子问题答案避免重复计算由小推大从小状态推出大状态核心重叠子问题 最优子结构 无后效性一句话递归暴力会重复算→用数组存中间结果→递推得出答案三、DP 解题标准四步法必背确定 dp 数组含义dp [i] 代表什么状态推导状态转移方程dp[i] ?确定初始化dp [0]、dp [1] 初始值确定遍历顺序从前到后 / 从后往前四、入门例题 1斐波那契数列1. dp 定义dp [i]第 i 个斐波那契数2. 转移方程dp[i] dp[i-1] dp[i-2]3. 初始化dp[0]0dp[1]14. 代码#include iostream #include vector using namespace std; int fib(int n) { if(n 1) return n; vectorint dp(n1); dp[0] 0; dp[1] 1; for(int i 2; i n; i) { dp[i] dp[i-1] dp[i-2]; } return dp[n]; } int main() { cout fib(10); return 0; }五、入门例题 2爬楼梯最经典 DP 入门题目一次爬 1 阶或 2 阶求爬到 n 阶多少种方法思路dp [i]到第 i 阶的方法数最后一步要么 1 阶、要么 2 阶转移dp[i] dp[i-1] dp[i-2]int climbStairs(int n) { if(n 2) return n; vectorint dp(n1); dp[1] 1; dp[2] 2; for(int i 3; i n; i) { dp[i] dp[i-1] dp[i-2]; } return dp[n]; }六、空间优化滚动变量常数空间DP 很多题可以不用数组只用两个变量int climbStairs(int n) { if(n2) return n; int a1,b2,c; for(int i3;in;i) { c ab; a b; b c; } return b; }七、一维 DP 进阶打家劫舍不能偷相邻房间求最大金额dp [i]前 i 间房最大金额选当前dp [i-2]nums [i]不选当前dp [i-1]转移dp[i] max(dp[i-1], dp[i-2]nums[i])八、今日核心总结DP 核心拆分子问题 记录状态 状态转移固定四步定 dp 含义→写转移→初始化→遍历入门一维 DP斐波那契、爬楼梯、打家劫舍一维 DP 大多可以用两个变量做空间优化递归是自顶向下DP 递推是自底向上九、课后练习用 DP 手写斐波那契数列独立写出爬楼梯完整 DP 代码尝试用常数空间优化代码
