题目描述（中等难度）

机器人从左上角走到右下角，只能向右或者向下走。输出总共有多少种走法。

解法一 递归

求 ( 0 , 0 ) 点到（ m - 1 , n - 1） 点的走法。

（0，0）点到（m - 1 , n - 1） 点的走法等于（0，0）点右边的点 （1，0）到（m - 1 , n - 1）的走法加上（0，0）点下边的点（0，1）到（m - 1 , n - 1）的走法。

而左边的点（1，0）点到（m - 1 , n - 1） 点的走法等于（2，0） 点到（m - 1 , n - 1）的走法加上（1，1）点到（m - 1 , n - 1）的走法。

下边的点（0，1）点到（m - 1 , n - 1） 点的走法等于（1，1）点到（m - 1 , n - 1）的走法加上（0，2）点到（m - 1 , n - 1）的走法。

然后一直递归下去，直到 （m - 1 , n - 1） 点到（m - 1 , n - 1） ，返回 1。

时间复杂度：

空间复杂度：

遗憾的是，这个算法在 LeetCode 上超时了。我们可以优化下，问题出在当我们求点 （x，y）到（m - 1 , n - 1） 点的走法的时候，递归求了点 （x，y）点右边的点 （x + 1，0）到（m - 1 , n - 1）的走法和（x，y）下边的点（x，y + 1）到（m - 1 , n - 1）的走法。而没有考虑到（x + 1，0）到（m - 1 , n - 1）的走法和点（x，y + 1）到（m - 1 , n - 1）的走法是否是之前已经求过了。事实上，很多点求的时候后边的的点已经求过了，所以再进行递归是没有必要的。基于此，我们可以用 visited 保存已经求过的点。

时间复杂度：

空间复杂度：

解法二 动态规划

解法一是基于递归的，压栈浪费了很多时间。我们来分析一下，压栈的过程，然后我们其实完全可以省略压栈的过程，直接用迭代去实现。

如下图，如果是递归的话，根据上边的代码，从 （0，0）点向右压栈，向右压栈，到最右边后，就向下压栈，向下压栈，到最下边以后，就开始出栈。出栈过程就是橙色部分。

接下来两步同理，压栈，出栈。

我们现在要做的就是要省略压栈的过程，直接出栈。很明显可以做到的，只需要初始化最后一列为 1 ，然后 1 列，1 列的向前更新就可以了。有一些动态规划的思想了。

时间复杂度：O（m * n）。

空间复杂度：O（m）。

也有一个类似的想法。不过他是正向考虑的，和上边的想法刚好相反。如果把 dp [ i ] [ j ] 表示为从点 （0，0）到点 ( i，j）的走法。

上边解法公式就是 dp [ i ] [ j ] = dp [ i + 1 ] [ j ] + dp [ i ] [ j +1 ]。

这里的话就是 dp [ i ] [ j ] = dp [ i - 1 ] [ j ] + dp [ i ] [ j - 1 ]。就是用它左边的和上边的更新，可以结合下图。

这样的话，就是从左向右，从上到下一行一行更新（当前也可以一列一列更新）。

时间复杂度：O（m * n）。

空间复杂度：O（n）。

解法三 公式

我们用 R 表示向右，D 表示向下，然后把所有路线写出来，就会发现神奇的事情了。

R R R D D

R R D D R

R D R D R

……

从左上角，到右下角，总会是 3 个 R，2 个 D，只是出现的顺序不一样。所以求解法，本质上是求了组合数，N = m + n - 2，也就是总共走的步数。 k = m - 1，也就是向下的步数，D 的个数。所以总共的解就是

。

时间复杂度：O（m）。

空间复杂度：O（1）。

总

从递归，到递归改迭代，之前的题也都遇到过了，本质上就是省去压栈的过程。解法三的公式法，直接到问题的本质，很厉害。

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 查看详情