---

1359. 有效的快递序列数目

• 标签：数学、动态规划、组合数学
• 难度：困难

题目链接

• 1359. 有效的快递序列数目 - 力扣

题目大意

描述：给定 $n$ 个订单，每个订单需要先取件（$P_i$）再配送（$D_i$）。取件必须在配送之前。

要求：返回所有可能的有效序列数目，对 $10^9 + 7$ 取模。

说明：

• $1 \le n \le 500$。

示例：

• 示例：

输入：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)。

解题思路

思路 1：动态规划 / 组合数学

1. 核心思想

考虑增量构造。已知前 $i-1$ 个订单有 $f[i-1]$ 种合法序列，现在插入第 $i$ 个订单（$P_i$ 和 $D_i$），且 $P_i$ 必须在 $D_i$ 之前。

当前已有 $2(i-1)$ 个事件在前面。我们需要插入 $P_i$ 和 $D_i$ 两个事件。

先插入 $P_i$：有 $2(i-1)+1$ 个位置可以放。
再插入 $D_i$：必须在 $P_i$ 之后，所以有 $2(i-1)+2$ 个位置去掉 $P_i$ 所在的 $1$ 个无效位置，剩下 $2i-1$ 个位置。

所以：$f[i] = f[i-1] \times (2i-1) \times i$。

其中 $(2i-1)$ 是 $D_i$ 的可选位置数，$i$ 是 $P_i$ 的可选位置数... 不对，重新推导。

2. 递推公式推导

已有 $i-1$ 个订单，序列长度为 $2(i-1)$。

插入第 $i$ 个订单的 $P_i$ 和 $D_i$，且要求 $P_i$ 在 $D_i$ 之前。

可选的插入方式数 = $C(2i, 2) = i(2i-1)$，即在 $2i$ 个位置中选 $2$ 个位置放 $P_i$ 和 $D_i$，且顺序固定为 $P_i$ 在前。从 $2i$ 个位置选 $2$ 个的组合数等于 $C(2i, 2) = i(2i-1)$。

所以 $f[i] = f[i-1] \times i \times (2i-1)$。

初始条件 $f[1] = 1$。

3. 结合示例走一遍

$n=2$：

• $f[1] = 1$
• $f[2] = 1 \times 2 \times (4-1) = 2 \times 3 = 6$

思路 1：代码

class Solution:
    def countOrders(self, n: int) -> int:
        mod = 10**9 + 7
        ans = 1
        for i in range(2, n + 1):
            ans = ans * i * (2 * i - 1) % mod
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。