移动路线

题目描述

X 桌子上有 $m$ 行 $n$ 列的方格矩阵，左下角为 $(1,1)$ 、右上角为 $(m,n)$ 。蚂蚁从 $(1,1)$ 出发到 $(m,n)$ ，每步只能向上或向右走一格，且不能离开矩阵。求不同的移动路线总数。输入一行两个整数 $m,n$ （ $0 < m+n \le 20$ ），输出方案数。 $m=n=1$ 时路线数为 $1$ ；样例 $m=2,n=3$ 时路线数为 $3$ 。

思路

每条路线必然恰含 $m-1$ 步上、 $n-1$ 步右，总步数 $m+n-2$ ；路线与"在这 $m+n-2$ 步里选哪几步上"一一对应，答案为组合数 $C(m+n-2, m-1)$ 。计算可用乘法逐步累乘，无需建 DP 表， $m=1$ 或 $n=1$ 时自动得到 $1$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 22:50
# update_at: 2026-10-04 14:22

import sys
from math import comb


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    m, n = next(data), next(data)
    # 任一条路线都恰含 m-1 步"上"与 n-1 步"右"，路线只由这 m+n-2 步的顺序决定：
    # 在总步数里任选 m-1 个位置放"上"，其余放"右"，故答案为组合数。
    print(comb(m + n - 2, m - 1))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 05:11
 * update_at: 2026-10-05 05:11
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 题目数据：m, n 都是 int 范围内的正整数，且 m+n <= 20；用 ll 只是保险。
int m, n;

// 逐步累乘计算 C(N, k) = N*(N-1)*...*(N-k+1) / k*(k-1)*...*1。
// 顺序乘法再除以同阶分母，避免中间出现非整数。
ll comb(int N, int k) {
    if (k < 0 || k > N) return 0;
    if (k > N - k) k = N - k; // 利用 C(N,k) = C(N,N-k) 减少乘法次数
    ll num = 1;
    ll den = 1;
    for (int i = 0; i < k; i++) {
        num *= (N - i);
        den *= (i + 1);
    }
    return num / den;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n;

    // 每条路线恰含 m-1 步上、n-1 步右；路线数等价于从 m+n-2 步里选 m-1 步作为上步，
    // 答案 = C(m+n-2, m-1)。
    cout << comb(m + n - 2, m - 1) << endl;

    return 0;
}

目录

题目描述

思路

参考代码