Hard
题目描述
给你 n 笔订单，每笔订单都需要先取货（pickup）再交货（delivery）。
请你统计所有有效的取货/交货序列的数目，使得第 i 个订单的交货（delivery(i)）总是在取货（pickup(i)）之后。
由于答案可能很大，请返回答案对 10^9 + 7 取余的结果。
示例 1：
输入：n = 1
输出：1
解释：只有一种序列 (P1, D1)，交货 1 总是在取货 1 之后。
示例 2：
输入：n = 2
输出：6
解释：所有可能的序列有：
(P1,P2,D1,D2)，(P1,P2,D2,D1)，(P1,D1,P2,D2)，(P2,P1,D1,D2)，(P2,P1,D2,D1) 和 (P2,D2,P1,D1)。
这是一个无效的序列 (P1,D2,P2,D1)，因为取货 2 在交货 2 之后。
示例 3：
输入：n = 3
输出：90
约束条件：
- 1 <= n <= 500
提示：
- 使用排列组合理论，每次添加一对 (P, D)，直到 n 对。
解题思路
这道题是一道经典的组合数学问题。我们需要找到所有满足约束条件的序列数量。
核心思路：
我们可以用动态递推的方法来解决这个问题。假设我们已经有了 i-1 对有效的取货交货序列，现在要插入第 i 对 (Pi, Di)。
对于已有的 i-1 对序列，总共有 2*(i-1) 个位置。我们需要：
- 首先选择 Pi 的插入位置：有 2*(i-1)+1 个可能的位置
- 然后选择 Di 的插入位置：Di 必须在 Pi 之后，所以有 2*i 个位置可选
状态转移：
- 设 f(i) 表示 i 对订单的有效序列数量
- f(i) = f(i-1) × (2i-1) × 2i
- 初始状态：f(1) = 1
数学推导：
- f(1) = 1
- f(2) = f(1) × 3 × 4 = 1 × 3 × 4 = 12/2 = 6
- f(3) = f(2) × 5 × 6 = 6 × 5 × 6 = 180/2 = 90
实际上，这个公式可以简化为：f(n) = ((2n)!)/(2^n)
推荐解法： 使用递推公式，逐步计算每一项，避免计算大阶乘可能导致的溢出问题。
代码实现
class Solution {
public:
int countOrders(int n) {
const int MOD = 1e9 + 7;
long long result = 1;
for (int i = 2; i <= n; i++) {
result = (result * (2 * i - 1) % MOD * (2 * i)) % MOD;
}
return result;
}
};
class Solution:
def countOrders(self, n: int) -> int:
MOD = 10**9 + 7
result = 1
for i in range(2, n + 1):
result = (result * (2 * i - 1) * (2 * i)) % MOD
return result
public class Solution {
public int CountOrders(int n) {
const int MOD = 1000000007;
long result = 1;
for (int i = 2; i <= n; i++) {
result = (result * (2 * i - 1) % MOD * (2 * i)) % MOD;
}
return (int)result;
}
}
var countOrders = function(n) {
const MOD = 1e9 + 7;
let result = 1;
for (let i = 2; i <= n; i++) {
result = (result * (2 * i - 1) * (2 * i)) % MOD;
}
return result;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 需要循环 n-1 次进行递推计算 |
| 空间复杂度 | O(1) | 只使用常数个变量存储中间结果 |