मान लीजिए कि हमारे पास एक स्ट्रिंग S है। यह सेट {'D', 'I'} से वर्णों की एक स्ट्रिंग है। (D का अर्थ है "घटाना" और I का अर्थ है "बढ़ना")
अब मान लें कि एक वैध क्रमपरिवर्तन एक क्रमपरिवर्तन है 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 सरणी dp आकार (n + 1) x (n + 1)
. को परिभाषित करें -
इनिशियलाइज़ j :=0 के लिए, जब j <=n, अपडेट करें (j को 1 से बढ़ाएँ), करें -
-
डीपी [0, जे]:=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)
-
-
-
-
वापसी डीपी [एन, 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"
आउटपुट
3