跳转至

1359. 有效的快递序列数目

题目描述

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

计算所有有效的 取货 / 交付 可能的顺序，使 delivery(i) 总是在 pickup(i) 之后。

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

 

示例 1：

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

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

示例 3：

输入：n = 3
输出：90

 

提示：

  • 1 <= n <= 500

解法

方法一：动态规划

我们定义 \(f[i]\) 表示 \(i\) 个订单的所有有效的收件/配送序列的数目。初始时 \(f[1] = 1\)。

我们可以选择这 \(i\) 个订单中的任意一个作为最后一个配送的订单 \(D_i\)，那么它的收件订单 \(P_i\) 可以在之前 \(2 \times i - 1\) 的任意一个位置，剩下的 \(i - 1\) 个订单的配送/收件序列数目为 \(f[i - 1]\)，所以 \(f[i]\) 可以表示为：

\[ f[i] = i \times (2 \times i - 1) \times f[i - 1] \]

最终的答案即为 \(f[n]\)。

我们注意到 \(f[i]\) 的值只与 \(f[i - 1]\) 有关，所以可以用一个变量代替数组，降低空间复杂度。

时间复杂度 \(O(n)\)，其中 \(n\) 为订单数目。空间复杂度 \(O(1)\)。

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int countOrders(int n) {
        final int mod = (int) 1e9 + 7;
        long f = 1;
        for (int i = 2; i <= n; ++i) {
            f = f * i * (2 * i - 1) % mod;
        }
        return (int) f;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int countOrders(int n) {
        const int mod = 1e9 + 7;
        long long f = 1;
        for (int i = 2; i <= n; ++i) {
            f = f * i * (2 * i - 1) % mod;
        }
        return f;
    }
};

1
2
3
4
5
6
7
8
func countOrders(n int) int {
    const mod = 1e9 + 7
    f := 1
    for i := 2; i <= n; i++ {
        f = f * i * (2*i - 1) % mod
    }
    return f
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
const MOD: i64 = (1e9 as i64) + 7;

impl Solution {
    #[allow(dead_code)]
    pub fn count_orders(n: i32) -> i32 {
        let mut f = 1;
        for i in 2..=n as i64 {
            f = (i * (2 * i - 1) * f) % MOD;
        }
        f as i32
    }
}

评论