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.
1class Solution {
2 private static final int MOD = 1000000007;
3
4 public int countOrders(int n) {
5 int[][] dp = new int[n + 1][n + 1];
6 dp[0][0] = 1;
7
8 for (int p = 0; p <= n; ++p) {
9 for (int d = 0; d <= n; ++d) {
10 if (p < n) {
11 dp[p + 1][d] = (dp[p + 1][d] + (long)(n - p) * dp[p][d]) % MOD;
12 }
13 if (p > d) {
14 dp[p][d + 1] = (dp[p][d + 1] + (long)(p - d) * dp[p][d]) % MOD;
15 }
16 }
17 }
18
19 return dp[n][n];
20 }
21}This Java solution uses dynamic programming to fill a table dp[p][d] indicating the number of ways to arrange p pickups and d deliveries. It iteratively populates the table based on whether we add a new pickup or delivery, ensuring the constraints hold.
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.