问题描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

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

动态规划算法求最小路径（动态规划求不同路径）(1)

例如，上图是一个7 x 3 的网格。有多少可能的路径？

示例 1:

输入: m = 3, n = 2

输出: 3

解释:

从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下

2. 向右 -> 向下 -> 向右

3. 向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3

输出: 28

提示：

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 10 ^ 9
动态规划解决

注意这里机器人只能向下和向右移动，不能往其他方向移动，我们用dp[i][j]表示到坐标(i，j)这个格内有多少条不同的路径，所以最终的答案就是求dp[m-1][n-1]。

因为只能从上面或左边走过来，所以递推公式是

dp[i][j]=dp[i-1][j] dp[i][j-1]。dp[i-1][j]表示的是从上面走过来的路径条数。

dp[i][j-1]表示的是从左边走过来的路径条数。

动态规划算法求最小路径（动态规划求不同路径）(2)

那么边界条件是什么呢，如果Finish在第一行的任何位置都只有一条路径，同理Finish在第一列的任何位置也都只有一条路径，所以边界条件是第一行和第一列都是1。我们已经找到了递推公式，又找到了边界条件，所以动态规划代码很容易写出来，我们来看下

publicintuniquePaths(intm,intn){ int[][]dp=newint[m][n]; //第一列都是1 for(inti=0;i<m;i ){ dp[i][0]=1; } //第一行都是1 for(inti=0;i<n;i ){ dp[0][i]=1; } //这里是递推公式 for(inti=1;i<m;i ) for(intj=1;j<n;j ) dp[i][j]=dp[i-1][j] dp[i][j-1]; returndp[m-1][n-1]; }

动态规划优化

我们看上面二维数组的递推公式，当前坐标的值只和左边与上面的值有关，和其他的无关，这样二维数组造成大量的空间浪费，所以我们可以把它改为一维数组。

publicintuniquePaths(intm,intn){ int[]dp=newint[m]; Arrays.fill(dp,1); for(intj=1;j<n;j ) for(inti=1;i<m;i ) dp[i] =dp[i-1]; returndp[m-1];8}

这里的dp[i] =dp[i-1]；实际上就是dp[i]=dp[i] dp[i-1]，我们可以这样理解，上面的网格我们是一行一行计算的，dp[i]也就是上面红色的表示的是当前位置上面的值，dp[i-1]表示的是当前位置左边的值。

递归方式

这题除了动态规划以外，还可以把上面的动态规划改为递归的方式

publicintuniquePaths(intm,intn){ returnuniquePathsHelper(1,1,m,n); } //第i行第j列到第m行第n列共有多少种路径 publicintuniquePathsHelper(inti,intj,intm,intn){ //边界条件的判断 if(i>m||j>n) return0; if((i==m&&j==n)) return1; //从右边走有多少条路径 intright=uniquePathsHelper(i 1,j,m,n); //从下边走有多少条路径 intdown=uniquePathsHelper(i,j 1,m,n); //返回总的路径 returnright down; }

代码中有注释，很容易理解，但其实这种效率很差，因为他包含了大量的重复计算，我们画个图来看一下。

动态规划算法求最小路径（动态规划求不同路径）(3)

我们看到上面图中红色，黑色，还有那种什么颜色的都表示重复的计算，所以有一种方式就是把计算过的值使用一个map存储起来，用的时候先查看是否计算过，如果计算过就直接拿来用，看下代码

publicintuniquePaths(intm,intn){ returnuniquePathsHelper(1,1,m,n,newHashMap<>()); } publicintuniquePathsHelper(inti,intj,intm,intn,Map<String,Integer>map){ if(i>m||j>n) return0; if((i==m&&j==n)) return1; Stringkey=i "*" j; if(map.containsKey(key)) returnmap.get(key); intright=uniquePathsHelper(i 1,j,m,n,map); intdown=uniquePathsHelper(i,j 1,m,n,map); inttotla=right down; map.put(key,totla); returntotla; }

使用公式计算

我们要想到达终点，需要往下走n-1步，往右走m-1步，总共需要走n m-2步。他无论往右走还是往下走他的总的步数是不会变的。也就相当于总共要走n m-2步，往右走m-1步总共有多少种走法，很明显这就是一个排列组合问题，公式如下

动态规划算法求最小路径（动态规划求不同路径）(4)

排列组合的计算公式如下

动态规划算法求最小路径（动态规划求不同路径）(5)

公式为(m n-2)! / [(m-1)! * (n-1)!]

代码如下

publicintuniquePaths(intm,intn){ intN=n m-2; doubleres=1; for(inti=1;i<m;i ) res=res*(N-(m-1) i)/i; return(int)res; }

总结

这题使用动态规划是最容易理解也是最容易解决的，当然后面的递归和公式计算也能解决。

动态规划算法求最小路径（动态规划求不同路径）(6)

如果喜欢这篇文章还可以关注微信公众号“数据结构和算法”，查看更多的算法题

,