家居网站建设咨询,定制logo,互联网专业主要学什么,关于网站的推广文章题目描述#xff1a; 一个机器人位于一个 m x n 网格的左上角 #xff08;起始点在下图中标记为 “Start” #xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角#xff08;在下图中标记为 “Finish”#xff09;。 现在考虑网格中有障碍物。那… 题目描述 一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径 网格中的障碍物和空位置分别用 1 和 0 来表示。 题目链接 LeetCode-63-不同路径Ⅱ 解题思路详见注释~ 代码实现 class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {// 1. dp[i][j]含义走到(i,j)位置有 dp[i][j]种不同的路径// 2. 递推公式dp[i][j]依赖与 dp[i-1][j] 和 dp[i][j-1]的路径个数// 前提条件是 dp[i][j]!1// dp[i][j] dp[i-1][j] dp[i][j-1]// 3. 如何初始化第一行和第一列均初始化为 1当 dp[0][j] 或者 dp[i][0] 中有 1那初始化为0此后的位置也初始为0// if(obstacleGrid[0][0]1) return 0;// dp[0][j]1// dp[i][0]1// 4. 遍历顺序从左上到右下int m obstacleGrid.length;int n obstacleGrid[0].length;int[][] dp new int[m][n];if (obstacleGrid[0][0]1){return 0;}// 初始化列for (int i 0; i m obstacleGrid[i][0]0; i) {dp[i][0]1;}// 初始化行for (int i 0; i n obstacleGrid[0][i]0; i) {dp[0][i]1;}for (int i 1; i m; i) {for (int j 1; j n; j) {if (obstacleGrid[i][j]0){dp[i][j] dp[i-1][j] dp[i][j-1];}}}return dp[m-1][n-1];}
}
