Sponsored
Sponsored
This approach leverages recursion with memoization to calculate the number of valid sequences. The main idea is to determine how many ways we can arrange pickups and deliveries by handling one order at a time.
Time Complexity: O(N^2), where N is the number of orders, due to overlapping subproblems.
Space Complexity: O(N^2) due to storing results in the memoization dictionary.
1MOD = 10**9 + 7
2
3def countOrders(n):
4 memo = {}
5
6 def dp(p, d):
7 if p == 0 and d == 0:
8 return 1
9 if (p, d) in memo:
10 return memo[(p, d)]
11
12 ways = 0
13 if p > 0:
14 ways += p * dp(p - 1, d + 1)
15 if d > 0:
16 ways += d * dp(p, d - 1)
17
18 memo[(p, d)] = ways % MOD
19 return ways % MOD
20
21 return dp(n, 0)This Python function uses a recursive helper function dp(p, d) that tracks how many pickups and deliveries are remaining. If both pickups and deliveries are zero, it returns 1 as a valid sequence is formed. Otherwise, it calculates the possible sequences either by picking up an order or delivering an order, avoiding violating the sequence rule.
This approach uses a combinatorial method by calculating factorial operations iteratively to compute the number of valid sequences. It simplifies the problem by deriving a general formula.
Time Complexity: O(N), where N is the number of orders.
Space Complexity: O(1), as we only maintain a constant amount of extra space.
1#include <vector>
2using namespace std;
3
4const int MOD = 1e9 + 7;
5
6class Solution {
public:
int countOrders(int n) {
long long res = 1;
for(int i = 1; i <= n; ++i){
res = res * i % MOD;
res = res * (2 * i - 1) % MOD;
}
return res;
}
};This C++ solution iteratively applies a combinatorial formula that derives from possible positioning of deliveries after pickups. It computes using factorial increases corresponding to the number of current orders.