Given n
orders, each order consist in pickup and delivery services.
Count all valid pickup/delivery possible sequences such that delivery(i) is always after of pickup(i).
Since the answer may be too large, return it modulo 10^9 + 7.
Example 1:
Input: n = 1 Output: 1 Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.
Example 2:
Input: n = 2 Output: 6 Explanation: All possible orders: (P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) and (P2,D2,P1,D1). This is an invalid order (P1,D2,P2,D1) because Pickup 2 is after of Delivery 2.
Example 3:
Input: n = 3 Output: 90
Constraints:
1 <= n <= 500
Solution: Combination
Let dp[i] denote the number of valid sequence of i nodes.
For i-1 nodes, the sequence length is 2(i-1).
For the i-th nodes,
If we put Pi at index = 0, then we can put Di at 1, 2, …, 2i – 2 => 2i-1 options.
If we put Pi at index = 1, then we can put Di at 2,3,…, 2i – 2 => 2i – 2 options.
…
If we put Pi at index = 2i-1, then we can put Di at 2i – 1=> 1 option.
There are total (2i – 1 + 1) / 2 * (2i – 1) = i * (2*i – 1) options
dp[i] = dp[i – 1] * i * (2*i – 1)
or
dp[i] = 2n! / 2^n
C++
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua class Solution { public: int countOrders(int n) { constexpr int kMod = 1e9 + 7; long ans = 1; for (int i = 2; i <= n; ++i) ans = ans * i * (2 * i - 1) % kMod; return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment