扬中门户,seo 怎么做到百度首页,天津建设工程计价网站,视频网站自己做服务器今日任务 62.不同路径 63. 不同路径 II 62.不同路径 - Medium 题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 一个机器人位于一个 m x n 网格的左上角 #xff08;起始点在下图中标记为 “Start” #xff09;。 机器人每次只…今日任务 62.不同路径 63. 不同路径 II 62.不同路径 - Medium 题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台 一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。 问总共有多少条不同的路径 思路dp[i][j] 表示从第 i,j 格到终点的路径数量从终点向起点遍历。时间复杂度O(m × n)空间复杂度O(m × n) class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m, vectorint(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 - Medium
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台 一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径 网格中的障碍物和空位置分别用 1 和 0 来表示。 思路在 62.不同路径 的基础上每一步先判断该位置是否有障碍物如果有此位置的dp值为0。时间复杂度O(n × m)n、m 分别为obstacleGrid 长度和宽度空间复杂度O(n × m)
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) //如果在起点或终点出现了障碍直接返回0return 0;vectorvectorint dp(m, vectorint(n, 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];}}return dp[m - 1][n - 1];}
};今日总结
题目二相较于题目一在初始化时要注意碰到障碍物时的处理
