直接回答

动态规划是把问题分解为重叠子问题，保存子问题的解避免重复计算的优化方法。适用前提是问题具有最优子结构（最优解由子问题最优解构成）和重叠子问题。一般思路：定义状态、推导状态转移方程、确定边界初值、安排计算顺序。

展开解析

以斐波那契为例：朴素递归是指数级，因为 f(n-2) 被反复计算；存下已算结果（记忆化）或自底向上填表（递推）就降到 O(n)。设计状态是难点，常用套路是"以 i 结尾的最优值"或"前 i 个元素的最优值"，如背包问题 dp[i][w] 表示前 i 件物品容量 w 下的最大价值。优化手段：转移只依赖上一行时滚动数组压缩空间。与分治的区别在于子问题是否重叠；与贪心的区别在于 DP 枚举决策而贪心只做局部最优选择。易错点：状态定义后转移方程漏情况、遍历顺序错（完全背包正序、01 背包逆序）、边界初始化随意。验证技巧：先用小规模手算对照。追问：如何降维、如何输出具体方案（记录决策路径回溯）。