一句话答案

DP 四步：定义状态→写转移方程→确定初始值→确定遍历顺序，核心条件：最优子结构+重叠子问题。

核心要点

经典模型：

模型	例题	转移
线性DP	最长递增子序列	dp[i]=max(dp[j]+1)
背包	0-1背包	dp[i][w]=max(不选,选)
区间DP	戳气球	dp[i][j]=max(dp[i][k]+dp[k][j])

空间优化： 二维→一维滚动数组

追问与易错

追问方向：

• DP 和贪心的区别？
• 怎么判断一个题能用 DP？
• 空间优化的思路？

易错点：

• ❌ DP 能解决所有优化问题——需要最优子结构+重叠子问题
• ❌ 二维 DP 都能优化为一维——取决于依赖关系

💡 记忆锚点

DP四步走口诀"状态转移初始序"：先定义dp[i]表示什么（状态），再找dp[i]和前面的关系（转移方程），确定起点值（初始化），最后决定填表方向（遍历顺序）。DP和贪心的区别：DP回头看所有子问题取最优，贪心只看眼前最优不回头。能用DP的前提：大问题的最优解包含子问题的最优解（最优子结构）+子问题反复出现（重叠子问题）。