【Leetcode】62.不同路径

题目

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

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

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

image.png

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

说明：m 和 n 的值均不超过 100。

示例 1:

示例 2:

题解

这道题拿到题目我觉得大家的第一反应都是这应该是递归的题目,因为我们可以转化为子问题，但是这样暴力肯定会超时,就不用尝试了。其实在该题递归的方法就是从上面到下面不断的去尝试,如果我们能记住之前的结果,就对我们下一步有帮助,所以想到了DP的方法。

格子中的数字代表当前的方法.

初始状态

当前这个状态只和左边和上边的格子有关系.

2.png

依次求解

3.png

于是我们可以得到状态转移方程：

java代码

优化

上面图3我们在求解的时候,我们是一行一行求解的,实际上我们只需要记录遍历到(i, j)这个位置的时候当前行有几种路径,如果遍历到(i, m-1)的时候,替换掉这一行对应列的路径即可，于是状态转移方程编程:

res[j] = res[j] + res[j-1]

有的同学可能还是不理解,我在代码里面打印了一些信息方便理解：

Math

这个题其实可以用排列组合的方式来做。这其实是最开始想到的方法。

以模拟的[4, 7]的例子,每一条路径：

向右的肯定有6步;

向左的肯定有3步;

问题即为:c(9,3) = (9 * 8 * 7) / (1 * 2 * 3) = 84

组合数公式：c(m,n) = m! / (n! * (m - n)!)

java代码

java直接套用公式会越界,下面结果我用long存储:

需要稍微化简一下,化简的过程就是我求解c(9,3)的第二步骤。

python代码

python代码就比较凶残了,一行代码搞定:

贴一下DP版本的代码

热门阅读