知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 09 - 不同路径 ## 题目(LeetCode 62) m×n 网格,从左上角到右下角,每次只能向下或向右移动一步,有多少条不同路径? ``` 输入:m = 3, n = 4 输出:10 ``` ## 大白话理解 到达每个格子只有两种方式:从上面来,或从左边来。 ``` ┌───┬───┬───┬───┐ │ S │ → │ → │ │ ├───┼───┼───┼───┤ │ ↓ │ │ │ │ ├───┼───┼───┼───┤ │ │ │ │ E │ └───┴───┴───┴───┘ 到达 E 的路径数 = 从上面来的路径数 + 从左边来的路径数 ``` ## 四步法 ``` 第 1 步:dp[i][j] = 从左上角到达 (i,j) 的路径数 第 2 步:dp[i][j] = dp[i-1][j] + dp[i][j-1] 从上面来:dp[i-1][j] 条路径 从左边来:dp[i][j-1] 条路径 两者相加 第 3 步: 第一行 dp[0][j] = 1(只能一直向右走,只有 1 条路) 第一列 dp[i][0] = 1(只能一直向下走,只有 1 条路) 第 4 步:从左到右,从上到下 ``` ### 为什么第一行和第一列都是 1? ``` 第一行:从 (0,0) 到 (0,j),只能一直向右走,没有其他选择 → 只有 1 条路径 第一列:从 (0,0) 到 (i,0),只能一直向下走,没有其他选择 → 只有 1 条路径 如果不初始化,dp[0][j] 和 dp[i][0] 会是 0,导致整个表格都是 0 ``` ## 手动模拟(m=3, n=4) ``` 初始化第一行和第一列: 0 1 2 3 0 [ 1 1 1 1 ] 1 [ 1 _ _ _ ] 2 [ 1 _ _ _ ] 逐格填写: dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2 dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3 dp[1][3] = dp[0][3] + dp[1][2] = 1 + 3 = 4 dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3 dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6 dp[2][3] = dp[1][3] + dp[2][2] = 4 + 6 = 10 最终 dp 表格: 0 1 2 3 0 [ 1 1 1 1 ] 1 [ 1 2 3 4 ] 2 [ 1 3 6 10] 答案 = dp[2][3] = 10 ✓ ``` ## 代码 ```java public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) dp[i][0] = 1; for (int j = 0; j < n; j++) dp[0][j] = 1; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n - 1]; } ``` ### 空间优化到一维 ``` dp[i][j] 只依赖 dp[i-1][j](正上方)和 dp[i][j-1](左边) 可以用一维数组滚动更新 dp[j] 在更新前 = 上一行的 dp[i-1][j] dp[j-1] 已经更新 = 当前行的 dp[i][j-1] ``` ```java public int uniquePaths(int m, int n) { int[] dp = new int[n]; Arrays.fill(dp, 1); // 第一行全为 1 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[j] += dp[j - 1]; // dp[j] = 上方 + 左方 } } return dp[n - 1]; } ``` ### 一维优化的手动模拟(m=3, n=4) ``` 初始:dp = [1, 1, 1, 1](第一行) i=1(第二行): j=1: dp[1] += dp[0] → dp[1] = 1+1 = 2 j=2: dp[2] += dp[1] → dp[2] = 1+2 = 3 j=3: dp[3] += dp[2] → dp[3] = 1+3 = 4 dp = [1, 2, 3, 4] i=2(第三行): j=1: dp[1] += dp[0] → dp[1] = 2+1 = 3 j=2: dp[2] += dp[1] → dp[2] = 3+3 = 6 j=3: dp[3] += dp[2] → dp[3] = 4+6 = 10 dp = [1, 3, 6, 10] 答案 = dp[3] = 10 ✓ ``` ## 变体:不同路径 II(LeetCode 63)— 有障碍物 ``` 障碍物处无法通过,dp 值设为 0 grid = [[0,0,0], [0,1,0], [0,0,0]] 输出:2(障碍物在中间,只有两条路绕过去) ``` ```java public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length, n = obstacleGrid[0].length; int[] dp = new int[n]; dp[0] = 1; // 起点 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (obstacleGrid[i][j] == 1) { dp[j] = 0; // 障碍物,路径数为 0 } else if (j > 0) { dp[j] += dp[j - 1]; } } } return dp[n - 1]; } ``` ## 一句话总结 `dp[i][j] = dp[i-1][j] + dp[i][j-1]`,第一行第一列初始化为 1。可以用一维数组滚动优化空间。 --- 上一篇:[08 - 最长回文子串](./08-longest-palindrome.md) | 下一篇:[10 - 最大子数组和](./10-max-subarray.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入