本文共 2154 字,大约阅读时间需要 7 分钟。
话不多说先看算法效率:
题目描述: 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。 问总共有多少条不同的路径?示例:
输入: m = 3, n = 2
输出: 3 解释: 从左上角开始,总共有 3 条路径可以到达右下角。
这道题我们采用动态规划来解决:
题目要我们求出从机器人到星星有几条路,实际上等效于星星到机器人有几条路,那么我们设置一个数组paths[m+1][n+1],其中m,n分别是网格的行与列,paths[i][j]表示从机器人起点到第i行第j列有几条路径 ,那么paths[1][j]=1(1=<j<=n),paths[i][1]=1(1=<i<=m),状态转移方程如下:paths[i][j]=paths[i-1][j]+paths[i]
接下来我们利用代码来实现:
public class Solution { public int uniquePaths(int m, int n) { int[][] paths = new int[m+1][n+1]; for(int i=1;i<=m;i++){ paths[i][1]=1; } for(int j=1;j<=n;j++){ paths[1][j]=1; } for(int i=2;i<=m;i++){ for(int j=2;j<=n;j++){ paths[i][j]=paths[i-1][j]+paths[i][j-1]; } } return paths[m][n]; }}
还有一道此题的升级版:,基本方法与上面一致,但是要稍微做点修改,读者可以参考下面代码,这里我不细讲了。
public class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; int[][] paths = new int[m+1][n+1]; boolean flag = false; for(int i=1;i<=m;i++){ if(obstacleGrid[i-1][0]==1){ paths[i][1]=0; flag = true; }else{ if(!flag){ paths[i][1]=1; }else{ paths[i][1]=0; } } } flag = false; for(int j=1;j<=n;j++){ if(obstacleGrid[0][j-1]==1){ paths[1][j]=0; flag = true; }else{ if(!flag){ paths[1][j]=1; }else{ paths[1][j]=0; } } } for(int i=2;i<=m;i++){ for(int j=2;j<=n;j++){ if(obstacleGrid[i-1][j-1]==0){ paths[i][j]=paths[i-1][j]+paths[i][j-1]; } } } return paths[m][n]; }}
上面代码击败率如下:
转载地址:http://dolzi.baihongyu.com/