1359. Count All Valid Pickup and Delivery Options
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.
c++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
long dp[501][501];
int mod = 1e9 + 7;
long factorials[501];
long helper(int pickUp, int delivery) {
if(delivery < 0) return 0;
if(pickUp == 0) return factorials[delivery];
if(dp[pickUp][delivery] != -1) return dp[pickUp][delivery];
dp[pickUp][delivery] = (helper(pickUp - 1, delivery + 1) * pickUp % mod + helper(pickUp, delivery - 1) * delivery % mod) % mod;
return dp[pickUp][delivery];
}
public:
int countOrders(int n) {
memset(dp,-1,sizeof(dp));
factorials[1] = 1;
factorials[0] = 0;
for(int i = 2; i <= n; i++) {
factorials[i] = (factorials[i - 1] * i) % mod;
}
return helper(n,0);
}
};
|
