题解

题面描述：给定一个网格大小为 $m \times n$ ，从左上角出发到右下角，每步只能向右或向下，求不同路径条数。
思路（组合数学）：总共需要走 $m-1$ 次向下和 $n-1$ 次向右，共计 $N=m+n-2$ 步，从中选择 $k=m-1$ 次向下（或选择 $n-1$ 次向右）。答案为组合数： $C(N,k)=C(m+n-2,,m-1)$ 。可用逐步公式 $C(N,i)=C(N,i-1)\cdot\frac{N-i+1}{i}$ 计算，保持每步为整数。
- 时间复杂度： $O(\min(m,n))$
- 空间复杂度： $O(1)$

P3414.第1题-无人机飞行路径探索

1000ms

Tried: 12

Accepted: 6

Difficulty: 2

所属公司 : 大疆

算法与标签>数学

题目内容

在实际的无人机物流配送场景中，某配送区域被划分为 $m$ 行 $n$ 列的网格状飞行单元，每个单元格代表一个标准飞行区域（如 $100$ 米 $×100$ 米的安全飞行范围）。无人机从位于左上角的起始仓库出发，需要将货物送达右下角的配送点。为避免频繁转向影响飞行效率和避障系统稳定性，无人机每次只能执行两种基础飞行动作：向右平移一个单元格（对应飞行方向向东）或向下平移一个单元格（对应飞行方向向南）。请问，无人机从起始仓库到配送点共有多少种不同的可行飞行路径？

输入描述

输入为两行，每行一个正整数，分别代表配送区域 $m$ 行 $n$ 列

输出描述

输出为正整数

样例1

输入

3
7

输出

提示

$m>0，m<=200 n>0，n<=200$

输入

预期输出（选填）

题解

P3414.第1题-无人机飞行路径探索

题目内容

输入描述

输出描述

样例1

Status

Development

Support

About