知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 60 - 不同路径 ## 题目(LeetCode 62) m×n 网格,从左上角到右下角,每次只能向下或向右,有多少条不同路径? ## 解法 ```java class Solution { public int uniquePaths(int m, int n) { int[] dp = new int[n]; Arrays.fill(dp, 1); for (int i = 1; i < m; i++) for (int j = 1; j < n; j++) dp[j] += dp[j - 1]; return dp[n - 1]; } } ``` ## 复杂度 - 时间 O(mn),空间 O(n) ## 一句话总结 dp[i][j] = dp[i-1][j] + dp[i][j-1],空间优化为一维数组。 ## 空间压缩原理(为什么一维数组能work) ### 1. 二维递推与压缩前提 ```text dp[i][j] = dp[i-1][j] + dp[i][j-1] // 上 + 左 边界:第一行全 1(只能一直往右),第一列全 1(只能一直往下) ``` 算第 `i` 行时,只用得到「第 `i-1` 行同列」和「第 `i` 行前一列」,更早的行不再需要,所以**只保留一行**即可。 ### 2. 关键:同一个槽位"覆盖前 / 覆盖后"身份不同 ```java dp[j] += dp[j - 1]; // 等价于 dp[j] = dp[j] + dp[j-1] ``` | 表达式 | 取值时刻 | 实际代表的含义 | |---|---|---| | `dp[j]`(赋值前) | 覆盖前 | `dp[i-1][j]` → **上方** | | `dp[j-1]` | 已覆盖 | `dp[i][j-1]` → **左方** | | `dp[j]`(赋值后) | — | `dp[i][j]` | ![滚动数组里 dp[j-1] 与 dp[j] 相加](/images/algo-p506-2.svg) *图:滚动数组里 dp[j-1] 与 dp[j] 相加* ```text j-1 j ┌──────────┬──────────┐ 第 i 行 │ dp[j-1] │ dp[j] │ └──────────┴──────────┘ 本行新值(左) 上一行旧值(上) └────────┬─────────┘ 相加即 dp[i][j] ``` ### 3. 逐格推演(m=3, n=4) | 步骤 | 数组内容 | 对应 | |---|---|---| | 初始 `Arrays.fill(dp,1)` | `[1, 1, 1, 1]` | 第 0 行 | | i=1 | `[1, 2, 3, 4]` | 第 1 行 | | i=2 | `[1, 3, 6, 10]` | 第 2 行 | | 返回 | `dp[3] = 10` | 右下角,等于 C(5,2) | 验算 `i=2, j=2`:更新前 `dp[2]=3`(第 1 行,上),刚更新的 `dp[1]=3`(第 2 行,左),得 `dp[2]=6`,与二维表一致。 ### 4. 三个必须这样写的细节 1. **`Arrays.fill(dp, 1)` 一次承担两个初值**:填出第 0 行全 1;同时 `dp[0]` 因为 `j` 从 1 开始而永不被更新,始终为 1,正好代表第一列全 1。 2. **`j` 必须从左到右递增**:需要 `dp[j-1]` 是"本行刚算出来的新值";若倒着遍历,取到的是上一行的旧值,结果就错了。 3. **答案为 `dp[n-1]`**:最后一轮 `i = m-1` 结束后数组装的是最后一行,末尾元素即右下角。 ### 5. 通用口诀:遍历方向由"要新值还是旧值"决定 | 场景 | 需要的值 | 遍历方向 | |---|---|---| | 本题(不同路径) | 当前行的左值 | 从左到右(递增) | | 完全背包 | 当前行的左值(物品可重复) | 从左到右(递增) | | 0/1 背包 | 上一行的值(物品只用一次) | 从右到左(递减) | 判断方法:**这一格要用的那个格子,是这一轮刚更新的,还是上一轮留下的?** 刚更新的 → 顺着遍历;上一轮的 → 倒着遍历。 ## 解法二:数学组合 从 (0,0) 到 (m-1,n-1) 共走 m+n-2 步,其中 m-1 步向下,等价于 C(m+n-2, m-1)。 ```java class Solution { public int uniquePaths(int m, int n) { long res = 1; for (int i = 0; i < Math.min(m - 1, n - 1); i++) { res = res * (m + n - 2 - i) / (i + 1); } return (int) res; } } ``` ## 解法对比 | | 解法一(DP) | 解法二(数学组合) | |--|--------|--------| | 时间复杂度 | O(mn) | O(min(m,n)) | | 空间复杂度 | O(n) | O(1) | | 特点 | 通用,易理解 | 最优,需注意整数溢出 |
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入