C++-এ সকল বৈধ পিকআপ এবং ডেলিভারি অপশন গণনা

ধরি n সংখ্যক অর্ডারের একটি লিস্ট আছে, প্রতিটি অর্ডারে পিকআপ (pickup) এবং ডেলিভারি (delivery) সার্ভিস আছে। আমাদের সকল বৈধ পিকআপ/ডেলিভারি সিকোয়েন্স গণনা করতে হবে যাতে delivery[i] সবসময় pickup[i]-এর পরে থাকে। উত্তর খুব বড় হতে পারে, তাই 10^9 + 7 দিয়ে মডুলো (modulo) করে ফেরত দিতে হবে।

ইনপুট যদি 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, b নেবে –
- ((a mod m) + (b mod m)) mod m ফেরত দিন
mul() ফাংশন সংজ্ঞায়িত করুন যা a, b নেবে –
- ((a mod m) * (b mod m)) mod 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);    } }; main(){    Solution ob;    cout << (ob.countOrders(2)); }