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.
1const MOD = 1e9 + 7;
2
This JavaScript solution operates similarly to the C++ version, computing the result with a dynamic increment using factorial operations and adjusting mod conditions to prevent overflow.