一个机器人位于一个 m×n网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
一个整数m和一个整数n表示一个 m×n网格
不同的路径条数
输入
3 7
输出
28
输入
3 2
输出
3
从左上角开始，总共有3 条路径可以到达右下角。
输入
7 3
输出
28
输入
3 3
输出
6
给定一个 m×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) = (m−1)!(n−1)!(m+n−2)!.
考虑到题目保证答案小于等于 2×109，可以采用迭代计算组合数的方法，避免大数计算和溢出。
C++代码
Solution 类中。Python代码
Java代码
Solution 类封装解题方法。#include <iostream>
using namespace std;
class Solution {
public:
// 计算组合数 C(m+n-2, m-1)
int uniquePaths(int m, int n) {
// 由于组合数 C(m+n-2, m-1) 等价于 C(m+n-2, n-1)
int k = m < n ? m - 1 : n - 1;
long long res = 1;
// 迭代计算组合数
for (int i = 1; i <= k; i++) {
res = res * (m + n - 1 - i) / i;
}
return (int)res;
}
};
int main(){
int m, n;
// 读取输入的两个整数 m 和 n
while(cin >> m >> n){
Solution sol;
cout << sol.uniquePaths(m, n) << endl;
}
return 0;
}
# 定义 Solution 类封装功能函数
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# 选择较小的步数，计算 C(m+n-2, m-1) 等价于 C(m+n-2, n-1)
k = min(m, n) - 1
res = 1
# 通过循环迭代计算组合数
for i in range(1, k + 1):
res = res * (m + n - 1 - i) // i
return res
if __name__ == '__main__':
import sys
# 从标准输入读取数据
data = sys.stdin.read().split()
if data:
m = int(data[0])
n = int(data[1])
sol = Solution()
print(sol.uniquePaths(m, n))
import java.util.Scanner;
public class Main {
// 定义 Solution 类封装解题函数
static class Solution {
// 计算组合数 C(m+n-2, m-1)
public int uniquePaths(int m, int n) {
// 选择较小的数，计算 C(m+n-2, m-1) 等价于 C(m+n-2, n-1)
int k = Math.min(m, n) - 1;
long res = 1;
// 迭代计算组合数
for (int i = 1; i <= k; i++) {
res = res * (m + n - 1 - i) / i;
}
return (int)res;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取输入的两个整数 m 和 n
while (scanner.hasNextInt()) {
int m = scanner.nextInt();
int n = scanner.nextInt();
Solution sol = new Solution();
System.out.println(sol.uniquePaths(m, n));
}
scanner.close();
}
}