有效的快递序列数目Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你 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
# 思路
long[][] f = new long[n * 2 + 1][n + 2];
# 解法
class Solution {
public static final int MOD = (int)1e9 + 7;
public int countOrders(int n) {
long[][] f = new long[n * 2 + 1][n + 2];
f[0][0] = 1;
for(int i = 0; i < n * 2; i ++)
for(int j = 0; j <= Math.min(n, i); 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 (int)f[n + n][0];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 总结
- 分析出几种情况，然后分别对各个情况实现
