动态规划：leetcode 62 不同路径

本文讲解了如何解决机器人在 \(m \times n\) 网格中不同行走路径以及背后的动态规划思想。

一个机器人位于一个 \(m \times n\) 网格的左上角 （起始点在下图中标记为 “Start”）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？

示例1：

1输入：m = 3, n = 7
2输出：28

示例2：

1输入：m = 3, n = 2
2输出：3
3解释：
4从左上角开始，总共有 3 条路径可以到达右下角。
51. 向右 -> 向下 -> 向下
62. 向下 -> 向下 -> 向右
73. 向下 -> 向右 -> 向下

分析：机器人从 \((0,0)\) 位置触发，到 \((m - 1,n - 1)\) 终点。利用动归五部曲：

1. 确定dp数组(dp table)以及下标的含义
   • dp[i][j] :表示从 \((0,0)\) 出发，到 \((i,j)\) 有 dp[i][j] 条不同的路径。
2. 确定递推公式
   • dp[i][j-1] 表示 从 \((0,0)\) 的位置到 \((i,j-1)\) 有几条路径，dp[i-1][j] 同理。
   • dp[i][j] = dp[i-1][j] + dp[i][j-1]
3. dp数组的初始化
   • 因为从 \((0,0)\) 的位置到 \((i,0)\) 的路径只有一条，所以 dp[i][0] = 1
   • 同理，dp[0][j] = 1
   • 初始化代码是：

   1 for (int i = 0; i < m; i++) dp[i][0] = 1
   2 for (int j = 0; j < n; j++) dp[0][j] = 1
   

4. 确定遍历顺序
   • dp[i][j] 都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。
5. 举例推导dp数组

翻译:

• "English" |