一、动态规划核心思想1. 本质拆分重复子问题、记录中间结果、避免重复计算。 暴力递归会大量重复求解相同子问题DP 用数组 / 哈希存储子问题答案空间换时间。2. 四大核心要素状态定义 dp [i] /dp [i][j]清晰描述dp数组代表什么含义是 DP 最难一步。状态转移方程把大问题拆解为更小子问题写出递推公式。初始条件base case最小子问题不用推导、直接赋值。遍历顺序保证计算大状态时依赖的子状态已经算完。3. 适用场景判断满足两个条件才能用 DP最优子结构大问题最优解由若干子问题最优解构成重叠子问题递归过程反复计算相同子问题。4. 两种实现方式自顶向下记忆化递归备忘录递归 缓存遇到重复子问题直接查表适合思考、代码短。自底向上迭代 DP 数组从小到大循环填表效率更高无栈溢出工程常用。二、动态规划分类类别 1一维线性 DP单数组 dp [i]特征只有一个变化维度线性数组递推例题 1斐波那契数列题意F(0)0,F(1)1,F(n)F(n-1)F(n-2)求第 n 项。状态定义dp[i] 第 i 个斐波那契数转移方程dp[i] dp[i-1] dp[i-2]base casedp[0]0dp[1]1java// 自底向上DP public int fib(int n) { if(n 1) return n; int[] dp new int[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]; } // 空间优化仅保存前两项 O(1)空间 public int fibOpt(int n) { if(n 1) return n; int a 0, b 1; for(int i 2; i n; i){ int c a b; a b; b c; } return b; }例题 2爬楼梯 LeetCode70题意一次爬 1 或 2 阶求爬到 n 阶总方案数。dp [i]爬到第 i 阶的方案总数转移dp[i] dp[i-1] dp[i-2]basedp[1]1dp[2]2例题 3打家劫舍 LeetCode198一维 DP不能选相邻元素求最大和。 dp [i]前 i 户能偷的最大金额 转移dp[i] max(dp[i-1], dp[i-2]nums[i])类别 2二维 DPdp [i][j]双维度场景 1子序列 / 子串两个下标代表两段区间例题 1最长公共子序列 LCS LeetCode1143字符串 s1 长度 ms2 长度 ndp [i][j]s1 前 i 个字符、s2 前 j 个字符的最长公共子序列长度转移s1[i-1]s2[j-1]dp[i][j] dp[i-1][j-1] 1不相等dp[i][j] max(dp[i-1][j], dp[i][j-1])basedp[0][*]0、dp[*][0]0例题 2最长回文子串 LeetCode5dp [i][j]区间 [i,j] 是否为回文字符串 转移s [i]s [j] 且 (j-i2 || dp [i1][j-1])场景 2网格路径矩阵行走例题不同路径 LeetCode62m 行 n 列网格只能右 / 下走求从左上到右下路径数dp [i][j]走到 (i,j) 的路径总数转移dp[i][j] dp[i-1][j] dp[i][j-1]base第一行、第一列全为 1类别 3背包 DP最经典业务 DP 分类通用模型给定容量选物品求最值01 背包物品只能选 1 次 dp [j]容量 j 能装的最大价值 逆序遍历容量dp[j] max(dp[j], dp[j-w]v)完全背包物品无限选 正序遍历容量dp[j] max(dp[j], dp[j-w]v)多重背包物品限定 k 件分组背包物品分多组每组最多选一件例题零钱兑换 LeetCode322完全背包dp [i]凑金额 i 需要最少硬币数 转移dp[i] min(dp[i], dp[i-coins[k]]1)类别 4区间 DPdp [i][j]区间 [i,j] 最优解特征状态是一段连续区间大区间由小区间合并而来例题石子合并一堆石子分成左右两堆合并代价为两堆重量和求总最小代价。 dp [i][j]合并 i~j 石子的最小代价 转移枚举分割点 kdp[i][j] min(dp[i][k]dp[k1][j]) sum(i,j)遍历顺序先算短区间再算长区间。类别 5状态压缩 DP二进制 DP特征维度极大用二进制数字代表状态降低空间常用于棋盘、子集、排列问题旅行商 TSP 经典题。 dp [mask][u]mask 二进制表示已访问城市集合u 当前所在城市。类别 6树形 DP树上动态规划特征状态定义在树节点子树为子问题例题二叉树打家劫舍 LeetCode337 每个节点存两个状态dp [0]不偷当前节点子树最大值dp [1]偷当前节点子树最大值 后序遍历递归计算左右子树再合并。三、DP 通用解题模板做题固定流程判断是否 DP最优子结构 重叠子问题定义 dp 数组含义最关键找 base case 初始值推导状态转移方程确定循环遍历顺序正序 / 逆序 / 区间长度从小到大空间优化可选二维转一维、滚动数组输出目标 dp 值四、记忆化递归自顶向下 DP 模板以爬楼梯举例java运行int[] memo; public int climbStairs(int n) { memo new int[n1]; Arrays.fill(memo, -1); return dfs(n); } int dfs(int i){ if(i 1) return 1; if(i 2) return 2; if(memo[i] ! -1) return memo[i]; // 查表避免重复计算 memo[i] dfs(i-1) dfs(i-2); return memo[i]; }五、一维 / 二维 DP 空间优化规律一维线性 DP仅依赖前 1/2 项 → O (1) 变量替代数组01 背包二维转一维容量逆序防止物品重复选取LCS、路径类二维 DP可用滚动数组只保存上一行数据。