classSolution{public:intnumPermsDISequence(strings){constexprintkMod=1'000'000'007;constintn=s.length();// dp[i][j] := # of valid permutations w/ i + 1 digits, where s[i] is j-th// Digit of remaining digitsvector<vector<int>>dp(n+1,vector<int>(n+1));// When there's only one digit, the # of perms is 1for(intj=0;j<=n;++j)dp[0][j]=1;for(inti=1;i<=n;++i)if(s[i-1]=='I'){// s[i - 1] == 'I'// Calculate postfix sum to prevent duplicate calculationintpostfixsum=0;for(intj=n-i;j>=0;--j){postfixsum=(postfixsum+dp[i-1][j+1])%kMod;dp[i][j]=postfixsum;}}else{// s[i - 1] == 'D'// Calculate prefix sum to prevent duplicate calculationintprefix=0;for(intj=0;j<=n-i;++j){prefix=(prefix+dp[i-1][j])%kMod;dp[i][j]=prefix;}}returndp[n][0];}};
classSolution{publicintnumPermsDISequence(Strings){finalintkMod=1_000_000_007;finalintn=s.length();// dp[i][j] := # of valid permutations w/ i + 1 digits, where s[i] is j-th// Digit of remaining digitsint[][]dp=newint[n+1][n+1];// When there's only one digit, the # of perms is 1for(intj=0;j<=n;++j)dp[0][j]=1;for(inti=1;i<=n;++i)if(s.charAt(i-1)=='I'){// s[i - 1] == 'I'// Calculate postfix sum to prevent duplicate calculationintpostfixsum=0;for(intj=n-i;j>=0;--j){postfixsum=(postfixsum+dp[i-1][j+1])%kMod;dp[i][j]=postfixsum;}}else{// s[i - 1] == 'D'// Calculate prefix sum to prevent duplicate calculationintprefix=0;for(intj=0;j<=n-i;++j){prefix=(prefix+dp[i-1][j])%kMod;dp[i][j]=prefix;}}returndp[n][0];}}
classSolution{public:intnumPermsDISequence(strings){constexprintkMod=1'000'000'007;constintn=s.length();vector<int>dp(n+1);// When there's only one digit, the # of perms is 1for(intj=0;j<=n;++j)dp[j]=1;for(inti=1;i<=n;++i){vector<int>newDp(n+1);if(s[i-1]=='I'){// s[i - 1] == 'I'// Calculate postfix sum to prevent duplicate calculationintpostfixsum=0;for(intj=n-i;j>=0;--j){postfixsum=(postfixsum+dp[j+1])%kMod;newDp[j]=postfixsum;}}else{// s[i - 1] == 'D'// Calculate prefix sum to prevent duplicate calculationintprefix=0;for(intj=0;j<=n-i;++j){prefix=(prefix+dp[j])%kMod;newDp[j]=prefix;}}dp=move(newDp);}returndp[0];}};