题解

题面描述

给定一个 $m \times n$ 的网格，一个机器人从左上角（$Start$）出发，每次只能向下或者向右移动一步，目标是到达右下角（$Finish$）。求机器人从起点到终点一共可以走多少条不同的路径。输入为两个整数 $m$ 和 $n$，输出为不同的路径条数。

思路

机器人从起点到终点必须经过总共 $m+n-2$ 步，其中向下走 $m-1$ 步，向右走 $n-1$ 步。问题转化为在 $m+n-2$ 步中选择 $m-1$ 步为向下走（或者选择 $n-1$ 步为向右走），因此路径数为组合数
$C(m+n-2, m-1)$ = $\frac{(m+n-2)!}{(m-1)! \, (n-1)!}.$

Leetcode 91.不同路径-原题链接

题目内容

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

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

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

输入描述

一个整数$m$和一个整数$n$表示一个 $m × n$网格

输出描述

不同的路径条数

样例1

输入

3 7

输出

28

样例2

输入

3 2

输出

3

说明

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

1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

样例3

输入

7 3

输出

28

样例3

输入

3 3

输出

6

提示

• $1 <= m, n <= 20$
• 题目数据保证答案小于等于 $2 * 10^9$