C++ में वैध पिकअप और डिलीवरी विकल्पों की गणना

मान लीजिए हमारे पास n ऑर्डरों की सूची है, प्रत्येक ऑर्डर में पिकअप और डिलीवरी सेवाएं हैं। हमें सभी वैध पिकअप/डिलीवरी संभावित अनुक्रमों की गणना करनी है जैसे कि delivery[i] हमेशा pickup[i] के बाद हो। चूंकि उत्तर बहुत बड़ा हो सकता है, हम इसे मॉड्यूलो 10^9 + 7 पर लौटाएंगे।

यदि इनपुट 2 है, तो आउटपुट 6 होगा, क्योंकि सभी संभावित ऑर्डर हैं: (P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) और (P2,D2,P1,D1)। और ऑर्डर (P1,D2,P2,D1) वैध नहीं है क्योंकि पिकअप 2, डिलीवरी 2 के बाद है।

हल करने के चरण

m := 10^9 + 7
N := 550
आकार (N+5) x (N+5) का एक सरणी dp परिभाषित करें, इसे -1 से भरें
add() फ़ंक्शन परिभाषित करें: ((a % m) + (b % m)) % m लौटाएं
mul() फ़ंक्शन परिभाषित करें: ((a % m) * (b % m)) % m लौटाएं
solve() फ़ंक्शन परिभाषित करें जो inPickup, left, i, j लेता है
यदि i==0 और j==0 तो 1 लौटाएं
यदि dp[i][j] != -1 तो dp[i][j] लौटाएं
ret := 0, यदि i > 0 तो ret := add(ret, mul(left, solve(inPickup+1, left-1, i-1, j)))
यदि j > i तो ret := add(ret, mul(inPickup, solve(inPickup-1, left, i, j-1)))
dp[i][j] = ret वापस करें
मुख्य विधि से: solve(0, n, n, n) वापस करें

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 
typedef long long int lli; 
const int m = 1e9 + 7; 
const int N = 550; 
int dp[N + 5][N + 5]; 

lli add(lli a, lli b) { 
    return ((a % m) + (b % m)) % m; 
} 

lli mul(lli a, lli b) { 
    return ((a % m) * (b % m)) % m; 
} 

class Solution { 
public: 
    void pre() { 
        for (int i = 0; i < N; i++) { 
            for (int j = 0; j < N; j++) { 
                dp[i][j] = -1; 
            } 
        } 
    } 
    
    int solve(int inPickup, int left, int i, int j) { 
        if (i == 0 && j == 0) return 1; 
        if (dp[i][j] != -1) return dp[i][j]; 
        int ret = 0; 
        if (i > 0) { 
            ret = add(ret, mul(left, solve(inPickup + 1, left - 1, i - 1, j))); 
        } 
        if (j > i) { 
            ret = add(ret, mul(inPickup, solve(inPickup - 1, left, i, j - 1))); 
        } 
        return dp[i][j] = ret; 
    } 
    
    int countOrders(int n) { 
        pre(); 
        return solve(0, n, n, n); 
    } 
}; 

int main() { 
    Solution ob; 
    cout << (ob.countOrders(2)); 
    return 0; 
}