免费开发网站大全,上海国企排名100强,北京大良网站建设,本地wordpress预览62.不同路径
一个机器人位于一个 m x n 网格的左上角 #xff08;起始点在下图中标记为 “Start” #xff09;。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角#xff08;在下图中标记为 “Finish” #xff09;。
问总共有多少条不同的路径…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
思路
dp[m][n] 到达m,n的路径数目, 递推:dp[m][n] dp[m-1][n] dp[m][n-1]
到达m,n 就是从m-1, n 往右走 或者 从m, n-1 往下走
代码
class Solution {public int uniquePaths(int m, int n) {// dp[m][n] 到达m,n的路径数目// dp[m][n] dp[m-1][n] dp[m][n-1]int [][] dp new int [m][n];for(int i0; im; i){dp[i][0] 1;}for(int i0; in; 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
一个机器人位于一个 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
思路
首先还是明确, 该问题的某一状态可以由上一个状态推出 所以采用动态规划
①dp数组含义不变, 仍旧是到达m,n的路径数目
②递推 正常情况(未遇到障碍)也不变, dp[m][n] dp[m-1][n] dp[m][n-1]
但若遇到障碍,则dp[m][n] 0;
③在初始化时, 若首行与首列 遇到障碍, 在障碍右侧 / 下方的应全为0
④遍历顺序, 按行遍历 从上到下 从左到右
⑤举例推导
代码
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m obstacleGrid.length;int n obstacleGrid[0].length;//dp含义不变, 递推公式考虑障碍物, 若当前位置为障碍物,则设置为0int [][] dp new int[m][n];for(int i 0; i m; i){if(obstacleGrid[i][0] 1){break;}dp[i][0] 1;}for(int i 0; i n; i){if(obstacleGrid[0][i] 1){break;}dp[0][i] 1;}for(int i 1; i m; i){for(int j 1; j n; j){if(obstacleGrid[i][j] 1){dp[i][j] 0;}else{dp[i][j] dp[i-1][j] dp[i][j-1];}}}return dp[m-1][n-1];}
}
