电子商务网站建设和技术现状,论前端对网站建设的重要性,西安 网站 公司,网站建设需要企业目录
62. 不同路径
63. 不同路径 II
62. 不同路径
题目
62. 不同路径 - 力扣#xff08;LeetCode#xff09;
一个机器人位于一个 m x n 网格的左上角 #xff08;起始点在下图中标记为 “Start” #xff09;。
机器人每次只能向下或者向右移动一步。机器人试图达到…目录
62. 不同路径
63. 不同路径 II
62. 不同路径
题目
62. 不同路径 - 力扣LeetCode
一个机器人位于一个 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
思路
代码随想录62.不同路径
视频讲解LeetCode62.不同路径
动态规划五部曲
确定dp数组以及下标含义使用二维dp数组保存结果确定dp[i][j]为到达 (i, j) 有多少条不同的路径确定递推公式dp[i] dp[i - 1][j] dp[i][j - 1]因为只能沿两种方向移动初始化数组dp[i][0]1, dp[0][j]1因为从起点到(i, 0)和(0, j)的路径都只有一条确定遍历顺序由递推公式得遍历顺序为从左往右从上往下举例推导 题解
独立题解
class Solution {public int uniquePaths(int m, int n) {int[][] dp new int[m][n];dp[0][0]1;for(int i 0; i m; i) {for(int j 0; j n; j) {if(j!0)dp[i][j]dp[i][j-1];if(i!0)dp[i][j]dp[i-1][j];}}return dp[m-1][n-1];}
}参考题解 public static int uniquePaths(int m, int n) {int[][] dp new int[m][n];//初始化for (int i 0; i m; i) {dp[i][0] 1;}for (int i 0; i n; i) {dp[0][i] 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提示
m obstacleGrid.lengthn obstacleGrid[i].length1 m, n 100obstacleGrid[i][j] 为 0 或 1
思路
代码随想录不同路径II
视频讲解LeetCode63. 不同路径 II
动态规划五部曲
确定dp数组以及下标含义使用二维dp数组保存结果确定dp[i][j]为到达 (i, j) 有多少条不同的路径确定递推公式dp[i] dp[i - 1][j] dp[i][j - 1]因为只能沿两种方向移动注意判断题目所给数组的(i, j)位置是否有障碍有障碍则保持为0的初始状态初始化数组dp[i][0]1, dp[0][j]1因为从起点到(i, 0)和(0, j)的路径都只有一条注意遇到障碍之后直接结束数组的初始化确定遍历顺序由递推公式得遍历顺序为从左往右从上往下举例推导 题解
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m obstacleGrid.length;int n obstacleGrid[0].length;int[][] dp new int[m][n];for (int i 0; i m; i) {if (obstacleGrid[i][0] 1)break;dp[i][0] 1;}for (int j 0; j n; j) {if (obstacleGrid[0][j] 1)break;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];}
}
