知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 01 - DP 思维框架 ## 先搞清楚:什么是动态规划? ### 大白话理解 想象你在爬一座很高的山,山上有很多岔路。 ``` 暴力做法:每次都从山脚重新爬,试遍所有路线 → 你会发现很多路段是重复走的,浪费大量时间 DP 做法:每到一个岔路口,把"到这里的最优路线"记在石碑上 → 后面再经过这个岔路口,直接看石碑,不用重新走 → 这就是"记住之前算过的结果,避免重复计算" ``` 再举个生活例子: ``` 你要算 1+1+1+1+1+1+1+1 = ? 你算出来了:8 现在问你:1+1+1+1+1+1+1+1+1 = ?(多加了一个 1) 你不会重新从头加,而是直接说:8 + 1 = 9 这就是动态规划的核心思想:利用已经算过的结果,推出新的结果 ``` ### 适用条件(两个缺一不可) ``` 1. 最优子结构:大问题的最优解包含小问题的最优解 比如:最短路径问题,A→C 的最短路径一定经过 A→B 的最短路径 2. 重叠子问题:同一个子问题会被反复计算 比如:斐波那契 f(5) = f(4) + f(3) f(4) = f(3) + f(2) ← f(3) 被算了两次! ``` ### 注意:容易困惑的地方 ``` Q:DP 和"记忆化搜索"是一回事吗? A:本质一样,都是"记住算过的结果"。 记忆化搜索 = 自顶向下(递归 + 备忘录) DP 表格法 = 自底向上(循环填表) 面试中两种写法都行,但填表法更常见,因为没有递归栈的开销。 Q:所有递归都能改成 DP 吗? A:不是。只有满足"最优子结构 + 重叠子问题"的才行。 比如归并排序虽然是递归,但子问题不重叠,不是 DP。 ``` --- ## 解题四步法(万能模板) ``` 第 1 步:定义状态 — dp[i] 代表什么? 这是最关键的一步,状态定义对了,后面水到渠成 第 2 步:找转移方程 — dp[i] 怎么从前面的状态推出来? 想"最后一步":到达 dp[i] 之前的那一步是什么? 第 3 步:确定初始值 — dp[0] = ? dp[1] = ? 最小的子问题,不需要推导,直接给答案 第 4 步:确定遍历顺序 — 从小到大?从大到小? 原则:算 dp[i] 的时候,它依赖的状态必须已经算好了 ``` ### 为什么要按这四步来? ``` 因为 DP 的本质就是"填表格": 第 1 步决定了表格的含义(每个格子代表什么) 第 2 步决定了填表规则(怎么从已有格子推出新格子) 第 3 步决定了起点(哪些格子可以直接填) 第 4 步决定了填表顺序(先填哪个后填哪个) ``` --- ## 用斐波那契数列走一遍四步法 ### 问题 ``` f(0) = 0, f(1) = 1 f(n) = f(n-1) + f(n-2) 求 f(n) ``` ### 四步法 ``` 第 1 步:dp[i] = 第 i 个斐波那契数 第 2 步:dp[i] = dp[i-1] + dp[i-2] 第 3 步:dp[0] = 0, dp[1] = 1 第 4 步:从小到大(因为 dp[i] 依赖 dp[i-1] 和 dp[i-2]) ``` ### 为什么暴力递归慢?画个递归树就明白了 ``` 求 f(5) 的递归树: f(5) / \ f(4) f(3) ← f(3) 被算了 2 次 / \ / \ f(3) f(2) f(2) f(1) ← f(2) 被算了 3 次 / \ f(2) f(1) / \ f(1) f(0) f(3) 算了 2 次,f(2) 算了 3 次,f(1) 算了 5 次 n 越大,重复越多 → 时间复杂度 O(2^n),指数爆炸! ``` ### 手动模拟:用 DP 表格填一遍 ``` 求 f(6) 初始化:dp[0] = 0, dp[1] = 1 i=2: dp[2] = dp[1] + dp[0] = 1 + 0 = 1 i=3: dp[3] = dp[2] + dp[1] = 1 + 1 = 2 i=4: dp[4] = dp[3] + dp[2] = 2 + 1 = 3 i=5: dp[5] = dp[4] + dp[3] = 3 + 2 = 5 i=6: dp[6] = dp[5] + dp[4] = 5 + 3 = 8 画成表格: ┌───┬───┬───┬───┬───┬───┬───┐ │ i │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ ├───┼───┼───┼───┼───┼───┼───┤ │dp │ 0 │ 1 │ 1 │ 2 │ 3 │ 5 │ 8 │ └───┴───┴───┴───┴───┴───┴───┘ 每个格子只算一次 → O(n),比递归的 O(2^n) 快太多了 ``` ### 三种写法对比 ```java // 写法 1:暴力递归 — O(2^n),大量重复计算 int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } // 写法 2:记忆化搜索(自顶向下)— O(n) int fib(int n, int[] memo) { if (n <= 1) return n; if (memo[n] != 0) return memo[n]; // 算过了,直接返回 memo[n] = fib(n - 1, memo) + fib(n - 2, memo); return memo[n]; } // 写法 3:DP 表格法(自底向上)— O(n) int fib(int n) { if (n <= 1) return n; int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } // 写法 4:空间优化 — O(n) 时间,O(1) 空间 // 因为 dp[i] 只依赖 dp[i-1] 和 dp[i-2],不需要整个数组 int fib(int n) { if (n <= 1) return n; int prev2 = 0, prev1 = 1; for (int i = 2; i <= n; i++) { int curr = prev1 + prev2; prev2 = prev1; prev1 = curr; } return prev1; } ``` ### 空间优化的手动模拟 ``` 求 f(6),只用两个变量 初始:prev2 = 0, prev1 = 1 i=2: curr = 1 + 0 = 1 → prev2 = 1, prev1 = 1 i=3: curr = 1 + 1 = 2 → prev2 = 1, prev1 = 2 i=4: curr = 2 + 1 = 3 → prev2 = 2, prev1 = 3 i=5: curr = 3 + 2 = 5 → prev2 = 3, prev1 = 5 i=6: curr = 5 + 3 = 8 → prev2 = 5, prev1 = 8 返回 prev1 = 8 ✓ 为什么能这样优化? 因为每次只需要"前两个值",更早的值用不到了 就像火车只需要看前两节车厢,不需要记住所有车厢 ``` --- ## 再来一个完整例子:最小路径和(画表格法) ### 问题 ``` 给一个 m×n 的网格,每个格子有一个非负整数。 从左上角走到右下角,每次只能向右或向下走。 求路径上数字之和的最小值。 示例: grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]] 输出:7(路径 1→3→1→1→1 = 7) ``` ### 四步法 ``` 第 1 步:dp[i][j] = 从左上角走到 (i,j) 的最小路径和 第 2 步:到达 (i,j) 只有两种方式 — 从上面来或从左边来 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] 为什么?因为你只能向右或向下走,所以 (i,j) 的上一步 要么是 (i-1,j)(从上面来),要么是 (i,j-1)(从左边来) 选路径和更小的那个,再加上当前格子的值 第 3 步: dp[0][0] = grid[0][0](起点) 第一行:dp[0][j] = dp[0][j-1] + grid[0][j](只能从左边来) 第一列:dp[i][0] = dp[i-1][0] + grid[i][0](只能从上面来) 第 4 步:从左到右,从上到下(保证依赖的格子已经算好) ``` ### 手动模拟:画表格填一遍(这是理解的关键) ``` grid: dp 表格初始化: ┌───┬───┬───┐ ┌───┬───┬───┐ │ 1 │ 3 │ 1 │ │ │ │ │ ├───┼───┼───┤ ├───┼───┼───┤ │ 1 │ 5 │ 1 │ │ │ │ │ ├───┼───┼───┤ ├───┼───┼───┤ │ 4 │ 2 │ 1 │ │ │ │ │ └───┴───┴───┘ └───┴───┴───┘ 第 1 步:填起点 dp[0][0] = grid[0][0] = 1 ┌───┬───┬───┐ │ 1 │ │ │ ├───┼───┼───┤ │ │ │ │ ├───┼───┼───┤ │ │ │ │ └───┴───┴───┘ 第 2 步:填第一行(只能从左边来) dp[0][1] = dp[0][0] + grid[0][1] = 1 + 3 = 4 dp[0][2] = dp[0][1] + grid[0][2] = 4 + 1 = 5 ┌───┬───┬───┐ │ 1 │ 4 │ 5 │ ├───┼───┼───┤ │ │ │ │ ├───┼───┼───┤ │ │ │ │ └───┴───┴───┘ 第 3 步:填第一列(只能从上面来) dp[1][0] = dp[0][0] + grid[1][0] = 1 + 1 = 2 dp[2][0] = dp[1][0] + grid[2][0] = 2 + 4 = 6 ┌───┬───┬───┐ │ 1 │ 4 │ 5 │ ├───┼───┼───┤ │ 2 │ │ │ ├───┼───┼───┤ │ 6 │ │ │ └───┴───┴───┘ 第 4 步:填剩余格子 dp[1][1] = min(dp[0][1], dp[1][0]) + grid[1][1] = min(4, 2) + 5 = 2 + 5 = 7 从上面来是 4,从左边来是 2,选左边(更小) dp[1][2] = min(dp[0][2], dp[1][1]) + grid[1][2] = min(5, 7) + 1 = 5 + 1 = 6 从上面来是 5,从左边来是 7,选上面(更小) dp[2][1] = min(dp[1][1], dp[2][0]) + grid[2][1] = min(7, 6) + 2 = 6 + 2 = 8 从上面来是 7,从左边来是 6,选左边(更小) dp[2][2] = min(dp[1][2], dp[2][1]) + grid[2][2] = min(6, 8) + 1 = 6 + 1 = 7 从上面来是 6,从左边来是 8,选上面(更小) 最终 dp 表格: ┌───┬───┬───┐ │ 1 │ 4 │ 5 │ ├───┼───┼───┤ │ 2 │ 7 │ 6 │ ├───┼───┼───┤ │ 6 │ 8 │ 7 │ └───┴───┴───┘ 答案 = dp[2][2] = 7 ✓ 最优路径:(0,0)→(1,0)→(1,1) 不对,让我们回溯看看 从 dp[2][2]=7 回溯:来自 dp[1][2]=6(上面) 从 dp[1][2]=6 回溯:来自 dp[0][2]=5(上面) 从 dp[0][2]=5 回溯:来自 dp[0][1]=4(左边) 从 dp[0][1]=4 回溯:来自 dp[0][0]=1(左边) 路径:1 → 3 → 1 → 1 → 1 = 7 ✓ ``` ### 代码 ```java public int minPathSum(int[][] grid) { int m = grid.length, n = grid[0].length; int[][] dp = new int[m][n]; dp[0][0] = grid[0][0]; // 填第一行 for (int j = 1; j < n; j++) { dp[0][j] = dp[0][j - 1] + grid[0][j]; } // 填第一列 for (int i = 1; i < m; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } // 填剩余格子 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; } } return dp[m - 1][n - 1]; } ``` --- ## DP vs 贪心 vs 回溯 怎么区分? 这是初学者最容易困惑的地方。三种方法都能解决"做选择"的问题,但适用场景不同。 ### 大白话对比 ``` 回溯(暴力搜索): "我不知道哪个选择最好,那就每个都试一遍" → 穷举所有可能,一定能找到答案 → 但太慢了,时间复杂度通常是指数级 DP(动态规划): "我发现很多选择的中间过程是重复的,记住它们就不用重复算了" → 在回溯的基础上,消除重复子问题 → 需要满足:最优子结构 + 重叠子问题 贪心(贪心算法): "我每一步都选当前看起来最好的,最终结果也是最好的" → 不需要考虑所有可能,每步只做局部最优选择 → 需要满足:贪心选择性质(局部最优 = 全局最优) → 不是所有问题都能贪心! ``` ### 用一个例子说明区别 ``` 问题:用最少的硬币凑出 amount 元(硬币面值 [1, 3, 5]) 凑 11 元: 贪心做法(每次选最大面值): 11 - 5 = 6 → 选 5 6 - 5 = 1 → 选 5 1 - 1 = 0 → 选 1 结果:3 枚(5+5+1)✓ 碰巧对了 但如果硬币是 [1, 3, 4],凑 6 元: 贪心:6 - 4 = 2 → 选 4 2 - 1 = 1 → 选 1 1 - 1 = 0 → 选 1 结果:3 枚(4+1+1)✗ 错了! 最优:2 枚(3+3) → 贪心在这里失败了,因为局部最优 ≠ 全局最优 DP 做法: 考虑所有可能的"最后一枚硬币",取最小值 dp[6] = min(dp[6-1], dp[6-3], dp[6-4]) + 1 = min(dp[5], dp[3], dp[2]) + 1 → 一定能找到最优解 回溯做法: 穷举所有硬币组合,找最少的那个 → 一定能找到最优解,但最慢 ``` ### 怎么判断用哪种方法? ``` 问自己三个问题: 1. 问题要求"最优解"还是"所有方案"? → 所有方案 → 回溯 → 最优解 → 可能是 DP 或贪心 2. 局部最优能推出全局最优吗? → 能 → 贪心(比如活动选择、跳跃游戏) → 不能 → DP 3. 有没有重叠子问题? → 有 → DP → 没有 → 分治(归并排序、快排) 简单记忆: 回溯 = 暴力穷举(万能但慢) DP = 聪明的穷举(记住重复的) 贪心 = 不穷举(每步选最好的,但不一定对) ``` --- ## DP 的常见类型 ``` 1. 线性 DP:dp[i] 只依赖前面的状态 例题:爬楼梯、打家劫舍、最大子数组和、最长递增子序列 2. 二维 DP:dp[i][j] 依赖相邻的状态 例题:最长公共子序列、编辑距离、不同路径、最小路径和 3. 背包 DP:选或不选,有容量限制 例题:0-1 背包、完全背包、零钱兑换 4. 区间 DP:dp[i][j] 表示区间 [i,j] 的最优解 例题:最长回文子串、戳气球 5. 状态压缩 DP:用二进制表示状态 例题:旅行商问题 ``` --- ## 想不出转移方程怎么办? ``` 方法 1:画表格,手动填几个值,找规律 → 就像上面最小路径和的例子,填着填着规律就出来了 方法 2:想"最后一步" → 到达 dp[i] 的最后一步是什么? → 爬楼梯:最后一步是爬 1 阶还是 2 阶? → 打家劫舍:最后一家是偷还是不偷? → 零钱兑换:最后一枚硬币是哪个面值? 方法 3:想"选择" → 当前位置有哪些选择?每种选择对应什么状态? → 把所有选择列出来,取最优的那个 方法 4:先写暴力递归,再改成 DP → 递归的参数 = DP 的状态 → 递归的返回值 = DP 的值 → 递归的调用关系 = 转移方程 ``` --- ## 一句话总结 DP 就是"填表格":定义好 dp[i] 的含义,想清楚"最后一步"有哪些选择,转移方程就出来了。遇到想不通的,先画表格手动填几个值,规律自然浮现。 --- 下一篇:[02 - 爬楼梯](./02-climbing-stairs.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入