山东省临沂建设局网站,深圳平面设计深圳平面设计公司,辽宁建设工程信息网官网查询,wordpress title优化Java解决不同路径问题2
01题目
一个机器人位于一个 m x n 网格的左上角 #xff08;起始点在下图中标记为 “Start” #xff09;。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角#xff08;在下图中标记为 “Finish”#xff09;。
现在考虑网格中…Java解决不同路径问题2
01题目
一个机器人位于一个 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提示
m obstacleGrid.lengthn obstacleGrid[i].length1 m, n 100obstacleGrid[i][j] 为 0 或 1
02 知识点 二维数组 动态规划DP 特殊情况分析
03 我的题解
public class dongtai02 {public static void main(String[] args) {
// int[][] obstacleGrid new int[][]{
// {0,0,0},
// {0,1,0},
// {0,0,0}
// };int[][] obstacleGrid new int[][]{{0,1},{0,0},};System.out.println(uniquePathsWithObstacles(obstacleGrid));}public static int uniquePathsWithObstacles(int[][] obstacleGrid) {//m为行数n为列数int mobstacleGrid.length;int nobstacleGrid[0].length;
// 考虑两个特殊情况数组第一个为1是直接返回0
// 当数组中仅有一个数时返回1if (obstacleGrid[0][0]!0) {return 0;}if (m1n1) {return 1;}//用二维数组来记录走到每个格子需要多少种可能非边缘格子的可能数为左方和上方的和int[][] numsnew int[m][n];//给第一行和第一列赋初始值为1到达的可能为1种for (int i 1; i m; i) {//因为是边缘如果遇到石头就直接退出剩下的格子到不了默认为0if (obstacleGrid[i][0]1) {break;}nums[i][0]1;}for (int i 1; i n; i) {if (obstacleGrid[0][i]1) {break;}nums[0][i]1;}
// 循环整个数组for (int i 1; i m; i) {for (int j 1; j n; j) {
// 如果原来的数组为1则结束本次循环if (obstacleGrid[i][j]1) {continue;}//到达当前的格子的可能数为到达上一个格子的可能数之和nums[i][j]nums[i-1][j]nums[i][j-1];}}return nums[m-1][n-1];}
}
