C++ এ DI সিকোয়েন্সের জন্য বৈধ পারমুটেশন

ধরুন আমাদের একটি স্ট্রিং S আছে। এটি {'D', 'I'} সেট থেকে অক্ষরের একটি স্ট্রিং। (D মানে "হ্রাস" এবং আমার মানে "বাড়ছে")

এখন বিবেচনা করুন একটি বৈধ স্থানচ্যুতি হল P[0], P[1], ..., P[n] পূর্ণসংখ্যার {0 থেকে n}, যাতে সকল i জন্য, এটি এই নিয়মগুলি পূরণ করে:

যদি S[i] =='D', তাহলে P[i]> P[i+1];
অন্যথায় যখন S[i] =='I', তখন P[i]

আমাদের খুঁজে বের করতে হবে কত বৈধ পারমুটেশন আছে? উত্তরটি অনেক বড় হতে পারে, তাই আমরা মোড 10^9 + 7 ব্যবহার করে ফিরে আসব।

সুতরাং, যদি ইনপুটটি "IDD" এর মতো হয়, তাহলে আউটপুট হবে 3, তাই তিনটি ভিন্ন স্থানান্তর হবে, এগুলো হল (0,3,2,1), (1,3,2,0), ( 2,3,1,0)।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n :=S
এর আকার
একটি 2D অ্যারে ডিপি আকারের (n + 1) x (n + 1) সংজ্ঞায়িত করুন
আরম্ভ করার জন্য j :=0, যখন j <=n, আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), করুন −
- dp[0, j] :=1
আরম্ভ করার জন্য i :=0, যখন i
- যদি S[i] 'I' এর মত হয়, তাহলে −
  - আরম্ভ করার জন্য j :=0, curr :=0, যখন j
    - curr :=(dp[i, j] + curr) mod m
    - dp[i + 1, j] =(dp[i + 1, j] + curr)
- অন্যথায়
  - j শুরু করার জন্য :=n - i - 1, curr :=0, যখন j>=0, আপডেট করুন (j 1 দ্বারা কম করুন), করুন −
    - curr :=(dp[i, j + 1] + curr) mod m
    - dp[i + 1, j] =(dp[i + 1, j] + curr)
dp[n, 0]
ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
class Solution {
   public:
   int numPermsDISequence(string S) {
      int n = S.size();
      vector<vector<int>> dp(n + 1, vector<int>(n + 1));
      for (int j = 0; j <= n; j++)
      dp[0][j] = 1;
      for (int i = 0; i < n; i++) {
         if (S[i] == 'I') {
            for (int j = 0, curr = 0; j < n - i; j++) {
               curr = (dp[i][j] + curr) % m;
               dp[i + 1][j] = (dp[i + 1][j] + curr) % m;
            }
         } else {
            for (int j = n - i - 1, curr = 0; j >= 0; j--) {
               curr = (dp[i][j + 1] + curr) % m;
               dp[i + 1][j] = (dp[i + 1][j] + curr) % m;
            }
         }
      }
      return dp[n][0];
   }
};
main(){
   Solution ob;
   cout << (ob.numPermsDISequence("IDD"));
}

ইনপুট

"IDD"