Description
Given n orders, each order consists of a pickup and a delivery service.
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
Solutions
Solution 1: Dynamic Programming
We define f[i] as the number of all valid pickup/delivery sequences for i orders. Initially, f[1] = 1.
We can choose any of these i orders as the last delivery order Di, then its pickup order Pi can be at any position in the previous 2 × i - 1, and the number of pickup/delivery sequences for the remaining i - 1 orders is f[i - 1], so f[i] can be expressed as:
The final answer is f[n].
We notice that the value of f[i] is only related to f[i - 1], so we can use a variable instead of an array to reduce the space complexity.
The time complexity is O(n), where n is the number of orders. The space complexity is O(1).
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(code-box)
