62.不同路径
题目：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7 输出：28
示例 2：
输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3 输出：28
示例 4：
输入：m = 3, n = 3 输出：6
提示：
1 <= m, n <= 100- 题目数据保证答案小于等于
2 * 109
思路：
这个问题可以通过动态规划来解决。我们可以使用一个二维数组 dp 来保存从起点到达每个格子的路径数量。
动态规划思路：
-
定义状态:
- 设
dp[i][j]为从起点 (0,0) 到达格子 (i,j) 的路径数。
- 设
-
状态转移方程:
- 机器人每次只能向下或者向右移动一步，所以到达
dp[i][j]的路径数等于从上方格子dp[i-1][j]到达的路径数与从左方格子dp[i][j-1]到达的路径数之和，即： dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]dp[i][j]=dp[i−1][j]+dp[i][j−1]
- 机器人每次只能向下或者向右移动一步，所以到达
-
初始条件:
- 起点
dp[0][0]的路径数为 1，因为机器人从起点开始，所以路径数为 1。 - 第一行和第一列的路径数也应该初始化，因为在这些位置上，机器人只能从左到右（对于第一行）或者从上到下（对于第一列）移动，因此：
- 对于第一行（
i = 0），dp[0][j] = 1（因为机器人只能一直向右移动）。 - 对于第一列（
j = 0），dp[i][0] = 1（因为机器人只能一直向下移动）。
- 对于第一行（
- 起点
-
计算路径数:
- 我们可以从左上角 (0,0) 开始，通过状态转移方程计算出每个格子的路径数，最终
dp[m-1][n-1]就是我们要的答案。
- 我们可以从左上角 (0,0) 开始，通过状态转移方程计算出每个格子的路径数，最终
上代码：
class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int>(n, 0));// 初始化第一行和第一列for (int i = 0; i < m; ++i) {dp[i][0] = 1;}for (int j = 0; j < n; ++j) {dp[0][j] = 1;}// 填充dp数组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];}
};
63. 不同路径 II
题目：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]] 输出：1
提示：
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j]为0或1
思路：
要解决这个问题，我们可以使用动态规划方法。与之前的没有障碍物的路径问题类似，但需要考虑障碍物的存在。
动态规划思路：
-
定义状态:
- 设
dp[i][j]为从起点 (0,0) 到达格子 (i,j) 的路径数。 - 如果
obstacleGrid[i][j] == 1，说明该格子为障碍物，不可通行，则dp[i][j] = 0。 - 否则，路径数为从上方格子
dp[i-1][j]和左方格子dp[i][j-1]到达的路径数之和。
- 设
-
状态转移方程:
dp[i][j]=obstacleGrid[i][j]==1?0:dp[i−1][j]+dp[i][j−1]dp[i][j] = \text{obstacleGrid}[i][j] == 1 ? 0 : dp[i-1][j] + dp[i][j-1]dp[i][j]=obstacleGrid[i][j]==1?0:dp[i−1][j]+dp[i][j−1] -
初始条件:
- 起点
dp[0][0]的路径数为1，但如果起点本身是障碍物，则dp[0][0] = 0。 - 第一行和第一列的路径数需要特别处理，因为只能从一个方向到达：
- 对于第一行（
i = 0），如果当前格子及其左侧没有障碍物，则路径数为 1，否则为 0。 - 对于第一列（
j = 0），如果当前格子及其上方没有障碍物，则路径数为 1，否则为 0。
- 对于第一行（
- 起点
-
计算路径数:
- 从左上角开始，通过状态转移方程计算出每个格子的路径数，最终
dp[m-1][n-1]就是我们要的答案。
- 从左上角开始，通过状态转移方程计算出每个格子的路径数，最终
上代码：
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();// 如果起点有障碍物，直接返回 0if (obstacleGrid[0][0] == 1) return 0;vector<vector<int>> dp(m, vector<int>(n, 0));// 初始化起点dp[0][0] = 1;// 初始化第一列for (int i = 1; i < m; ++i) {dp[i][0] = (obstacleGrid[i][0] == 0 && dp[i-1][0] == 1) ? 1 : 0;}// 初始化第一行for (int j = 1; j < n; ++j) {dp[0][j] = (obstacleGrid[0][j] == 0 && dp[0][j-1] == 1) ? 1 : 0;}// 填充dp数组for (int i = 1; i < m; ++i) {for (int j = 1; j < n; ++j) {if (obstacleGrid[i][j] == 0) {dp[i][j] = dp[i-1][j] + dp[i][j-1];}}}return dp[m-1][n-1];}
};
