Pro 62. 不同路径

题目描述：

一个机器人位于一个 m x n 网格的左上角 

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角

问总共有多少条不同的路径？

解题思路：

1.

最容易想到这是一道排列组合的题目，从左上角走到右下角向右和向下走的步数都是固定的，所以就是在(m-1)+(n-1)步中选择n-1步向下走的组合问题（也可以看成是选择m-1步向右走，一样的）。因此共有的不同路径数为。

代码如下：

//排列组合法，可以理解为一共要走m+n-2步，其中选择m-1步向下走 //使用double，否则m，n过大时会造成溢出 public int uniquePaths(int m, int n) { double result = factorial(m+n-2, n-1)/factorial(m-1,0); //System.out.println(result); return (int)result; } //阶乘函数 public double factorial(int start, int end){ double res = 1; for(double i=start; i>end; i--){ res = res*i; } return res; }

2.

第二种思路是动态规划的算法，在每一个位置，都是它上方的点向下走一步，或者它左边的点向右走一步。而第一行和第一列的所有点都只有一条路径能到达。

所有实现如下：

//m*n的网格即n行m列 //走到位置[i][j]的全部路径等于位置[i-1][j]的全部路径加位置[i][j-1]的全部路径 public int uniquePaths1(int m, int n){ int[][] paths = new int[n][m]; //第一行 for(int i=0; i<m; i++) paths[0][i] = 1; //第一列 for(int j=0; j<n; j++) paths[j][0] = 1; for(int i=1; i<m; i++){ for(int j=1; j<n; j++){ paths[j][i] = paths[j][i-1] + paths[j-1][i]; } } return paths[n-1][m-1]; }

Pro63. 不同路径||

题目描述：

和62题类似，只是在网格中多加了障碍。输入为一个二维数组，来表示网格，网格中的障碍物和空位置分别用 1 和 0 来表示。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

解题思路：

在有障碍物的情况下，如果某位置为障碍，则该点不可到达，将到达该点的所有路径数设为0。此外，在初始化第一行和第一列时，如果有一个格子为障碍，那么它右边/下边的格子均不可到达。

代码实现：

public int uniquePathsWithObstacles(int[][] obstacleGrid){ //若数组为空 if(obstacleGrid.length == 0) return 0; int len = obstacleGrid.length; int wid = obstacleGrid[0].length; int[][] paths = new int[len][wid]; //第一列 for(int i=0; i<len; i++){ if(obstacleGrid[i][0] == 1) break; paths[i][0] = 1; } //第一行 for(int j=0; j<wid; j++){ if(obstacleGrid[0][j] == 1) break; paths[0][j] = 1; } for(int i=1; i<len; i++){ for (int j=1; j<wid; j++){ //若该点为障碍，则到达该点的路径数为0 if(obstacleGrid[i][j] == 1) paths[i][j] = 0; else { paths[i][j] = paths[i-1][j] + paths[i][j-1]; } } } return paths[len-1][wid-1]; }

 

 

转载于:https://www.cnblogs.com/yingying7/p/11230929.html