题目描述

给你 n 笔订单，每笔订单都需要快递服务。

请你统计所有有效的 收件/配送 序列的数目，确保第 i 个物品的配送服务 delivery(i) 总是在其收件服务 pickup(i) 之后。

由于答案可能很大，请返回答案对 10^9 + 7 取余的结果。

样例

输入：n = 1
输出：1
解释：只有一种序列 (P1, D1)，物品 1 的配送服务（D1）在物品 1 的收件服务（P1）后。

输入：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 的收件服务（P2）不应在物品 2 的配送服务（D2）之后。

输入：n = 3
输出：90

限制

• 1 <= n <= 500

算法1

(动态规划) $O(n^2)$

1. 序列的长度为 $2n$，其有效下标从 $1$ 开始到 $2n$。
2. 设 $f(i, j)$ 表示已经统计完序列的前 $i$ 个位置，且当前有 $j$ 个物品 未匹配 的方案数。未匹配 的含义是，已经有了收件服务 P，但尚未有配送服务 D。
3. 初始时，$f(0, 0) = 1$，其余为 $0$。
4. 转移时，对于 $f(i, j)$ 考虑下一个位置放什么。如果下一个位置放一个配送服务 D，则共有 $j$ 种选择。如果下一个位置放一个新的收件服务 P，则有 $n - \frac{i - j}{2} - j$ 种选择，这是因为总共有 $n$ 个物品，已经完成匹配的有 $\frac{i - j}{2}$ 种，未匹配的有 $j$ 种。不需要担心 $\frac{i - j}{2}$ 除不尽，如果除不尽，则说明这不是一个合法状态，其对应的 $f(i, j)$ 一定是 $0$。所以转移方程有两个，$f(i + 1, j - 1) = f(i + 1, j - 1) + f(i,j) * j$，以及 $f(i + 1, j + 1) = f(i + 1, j + 1) + f(i, j) * (n - \frac{i - j}{2} - j)$。
5. 最终答案为 $f(2n, 0)$。

时间复杂度

• 状态数为 $O(n^2)$ 种，转移个数为常数，故总时间复杂度为 $O(n^2)$。

空间复杂度

• 需要额外 $O(n^2)$ 的空间记录转移数。

C++ 代码

class Solution {
public:
    #define LL long long
    int countOrders(int n) {
        const int mod = 1000000007;
        vector<vector<LL>> f(2 * n + 1, vector<LL>(n + 2, 0));
        f[0][0] = 1;

        for (int i = 0; i < 2 * n; i++)
            for (int j = 0; j <= min(i, n); j++) {
                f[i + 1][j + 1] = (f[i + 1][j + 1] 
                    + f[i][j] * (n - (i - j) / 2 - j)) % mod;
                if (j > 0)
                    f[i + 1][j - 1] = (f[i + 1][j - 1] + f[i][j] * j) % mod;
            }

        return f[2 * n][0];
    }
};

算法2

(数学) $O(n)$

1. 如果不考虑物品的先后顺序，则第一个位置必定是放置 P，然后剩下 2n - 1 个位置可选放对应的 D。然后，下一个 P 可能放在第二个位置（如果第一个 D 不在第二个位置），或者可能放在第三个位置（如果第一个 D 在第二个位置）；两种情况，第二个 P 对应的 D 都有 2n - 3 种选择，所以答案就是 (2n - 1) * (2n - 3) * ... * 1。
2. 考虑上顺序，再将以上答案乘上 n!。

时间复杂度

• 线性求出以上公式，时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的空间。

C++ 代码

class Solution {
public:
    #define LL long long
    int countOrders(int n) {
        const int mod = 1000000007;
        LL ans = 1;
        for (int i = 1; i <= n; i++)
            ans = ans * i * (2 * i - 1) % mod;

        return ans;
    }
};