哈尔滨道外区建设局官方网站,wordpress简称,做分销如何才能做起来,宁波网站建设公司比较好62. 不同路径 - 力扣#xff08;LeetCode#xff09;
一个机器人位于一个 m x n 网格的左上角 #xff08;起始点在下图中标记为 “Start” #xff09;。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角#xff08;在下图中标记为 “Finish” #…62. 不同路径 - 力扣LeetCode
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。
问总共有多少条不同的路径
示例 1 输入m 3, n 7
输出28
思路显然达到右下角只能是从左边或者上面来而每个位置也只能是从左边或者上面来考虑动态规划。
解决动态规划五步曲 第一步确定dp数组含义 题目是求到达右下角多少不同路径所以dp应该是二维数组dp[i][j],表示到达ij坐标位置有多少条不同路径。 第二步确定递推公式 每个位置也只能是从左边或者上面来所以达到ij位置dp[i][j]dp[i-1][j]dp[i][j-1]。 第三步dp数组初始化 首先i0时不管j等于多少dp[0][j]都是等于1同样j0时dp[i][0]都是等于1。 第四步确定遍历顺序 依次算出起点到每个位置的有多少条不同路径从左到右从上到下。 第五步举例推导dp数组
代码
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m, vectorint(n, 0));for(int j0;jn;j){dp[0][j]1;}for(int i0;im;i){dp[i][0]1;}for(int i1;im;i){for(int j1;jn;j){dp[i][j]dp[i-1][j]dp[i][j-1];}}return dp[m-1][n-1];}
};
63. 不同路径 II - 力扣LeetCode
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1 输入obstacleGrid [[0,0,0],[0,1,0],[0,0,0]]
输出2
解释3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有2条不同的路径
1. 向右 - 向右 - 向下 - 向下
2. 向下 - 向下 - 向右 - 向右
思路用动态规划但是需要去掉障碍物的位置。
解决动态规划五步曲 第一步确定dp数组含义 含义还是一样表示到达i,j位置的路径条数。 第二步确定递推公式 dp[i][j]dp[i-1][j]dp[i][j-1]如果遇到障碍怎么办也就是当前i,j位置没有路径过来递推直接跳过。 第三步dp数组初始化 首先初始化和上题类似但是如果障碍物在边界那障碍物右边的都是0或者障碍物下面的都是0 第四步确定遍历顺序 和上题一样 第五步举例推导dp数组
代码注意考虑障碍物在起点或者终点。
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int m obstacleGrid.size();int n obstacleGrid[0].size();if (obstacleGrid[m - 1][n - 1] 1 || obstacleGrid[0][0] 1) //如果在起点或终点出现了障碍return 0;vectorvectorint dp(m, vectorint(n, 0));for(int j0;jnobstacleGrid[0][j] 0;j){dp[0][j]1;}for(int i0;imobstacleGrid[i][0] 0;i){dp[i][0]1;}for(int i1;im;i){for(int j1;jn;j){if(obstacleGrid[i][j]1) continue;dp[i][j]dp[i-1][j]dp[i][j-1];}}return dp[m - 1][n - 1];}
};
