题解

题面描述

给定一个 $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)!}.$

考虑到题目保证答案小于等于 $2 \times 10^9$，可以采用迭代计算组合数的方法，避免大数计算和溢出。

代码分析

1. C++代码

   • 使用 LeetCode 风格，将解题函数封装在 Solution 类中。
   • 主函数中采用 ACM 模式读取输入输出。
   • 利用迭代法计算组合数，逐步累乘和除以相应因子，保证中间计算不会溢出。

2. Python代码

   • 同样封装为函数，注释详细解释各步。
   • 利用循环计算组合数。

3. Java代码

   • 使用 Solution 类封装解题方法。
   • 主函数中采用标准输入输出处理。
   • 同样用迭代法计算组合数。

C++

#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;
}

Python

# 定义 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))

Java

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();
    }
}

题目内容

一个机器人位于一个 $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$