मान लीजिए हमारे पास एक स्ट्रिंग 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] < P[i+1]।
हमें ढूंढना है कि कितने वैध क्रमपरिवर्तन हैं? उत्तर बहुत बड़ा हो सकता है, इसलिए मॉड्यूलो 10^9 + 7 में वापस करें।
उदाहरण के लिए, यदि इनपुट "IDD" है, तो आउटपुट 3 होगा।
हल करने का दृष्टिकोण
हम प्रीफिक्स योग अनुकूलन के साथ डायनामिक प्रोग्रामिंग का उपयोग करते हैं:
dp[i][j] = पहले i वर्णों के लिए वैध क्रमपरिवर्तनों की संख्या जो j पर समाप्त होती है
आधार: dp[0][j] = 1 सभी j के लिए
यदि S[i] == 'I': आगे से प्रीफिक्स योग संचित करें
यदि S[i] == 'D': पीछे से प्रीफिक्स योग संचित करें
उत्तर 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];
}
};
int main(){
Solution ob;
cout << (ob.numPermsDISequence("IDD"));
return 0;
}
इनपुट
"IDD"
आउटपुट
3
