DAY38 ||62.不同路径 |63. 不同路径 II
62.不同路径
题目：62. 不同路径 - 力扣（LeetCode）
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
- 输入：m = 3, n = 7
- 输出：28
示例 2：
- 输入：m = 2, n = 3
- 输出：3
解释： 从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 3：
- 输入：m = 7, n = 3
- 输出：28
示例 4：
- 输入：m = 3, n = 3
- 输出：6
五部曲·思路
1.确定dp数组以及下标的含义
二维数组。。
dp[i][j]表示从（0，0）出发，到（i,j)有多少条不同的路径
2.确定递推公式
dp[i][j]=dp[i-1][j]+dp[i][j-1]。
因为只能从两个方向来。。。。
3.dp数组初始化
首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条（只能一直向右），那么dp[0][j]也同理。
4.确定遍历顺序
从左到右，从上到下遍历
5.举例dp数组
代码
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;//起点出发一直向右的路径只有一条
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
题目：63. 不同路径 II - 力扣（LeetCode）
给定一个
m x n的整数数组grid。一个机器人初始位于 左上角（即grid[0][0]）。机器人尝试移动到 右下角（即grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。网格中的障碍物和空位置分别用
1和0来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于
2 * 109。示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释：3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右示例 2：
输入：obstacleGrid = [[0,1],[0,0]] 输出：1
五部曲
1.确定dp数组及其下标含义
在绕开了障碍物情况下，dp[i][j]表示从（0，0）出发，到（i,j)有多少条不同的路径
2.确定递推公式
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。但是！！(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）
3.dp数组初始化
和上题一样，最上边和最右边一栏的路径都只有一条。但是，如果遇到了障碍，那么以后的不同路径数都是0
4.遍历顺序
从左到右，从前到后
5.举例dp数组
如例一，那个路径数保持初始值0的就是障碍
代码
要注意区分网格数组（记录的空位置和障碍的情况）和dp数组（其含义是（i,j)的不同路径和）
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1)
return 0;//如果起点（obstacleGrid[0][0]）或终点（obstacleGrid[m-1][n-1]）有障碍物（1表示有障碍），则说明无法从起点到终点，所以直接返回 0。
vector<vector<int>> dp(m, vector<int>(n, 0));
//如果在某个位置有障碍物（obstacleGrid[i][0] == 1 或 obstacleGrid[0][j] == 1），则后续的位置就无法到达，因此后面的路径数保持为 0。
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 1) continue;//跳过有障碍物的点
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];//对于没有障碍物的点 (i, j)，它的路径数等于其上方位置 (i-1, j) 的路径数加上左边位置 (i, j-1) 的路径数
}
}
return dp[m - 1][n - 1];//最终返回 dp[m-1][n-1]，即到达终点位置的不同路径数。
}
};一刷跳过的两道题
343. 整数拆分 - 力扣（LeetCode）
96. 不同的二叉搜索树 - 力扣（LeetCode）