O(n^2) DP with O(n) space
Intuition\n Describe your first thoughts on how to solve this problem. \n- dp[j] in the i-th round memorizes the number of permutations ends with j for s[0:i].\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- dp[j] in the i-th round memorizes the number of permutations ends with j for s[0:i].\n\n- When s[i] is \'D\', update the ndp[j] with sum(dp[j:i]), which increases each element larger than j by one in the prefix.\n- When s[i] is \'I\', update ndp[j] with sum(dp[0:j-1]) while keeping the prefix.\n- Make use of the sum of prefix to get any sum(dp[j:i]) in $$O(1)$$\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n  int numPermsDISequence(string s) {\n      int n=s.size(),mod=1e9+7;\n      vector<int> dp{1};\n      for(int i=0;i<n;i++){\n          vector<int> pre{0}; //pre[i]=sum(dp[0:i-1])\n          int tmp=0;\n          for(auto j:dp) pre.emplace_back((j+pre.back())%mod);\n          vector<int> ndp;\n          if(s[i]==\'D\') for(int j=0;j<=i+1;j++) ndp.emplace_back(pre.back()>pre[j]?pre.back()-pre[j]:pre.back()-(pre[j]-mod)); //sum(dp[j,i])\n          else for(int j=0;j<=i+1;j++) ndp.emplace_back(pre[j]); //sum(dp[0],...,dp[j-1])\n          dp=ndp;\n      }\n      int result=0;\n      for(auto i:dp)  result=(result+i)%mod;\n      return result;\n  }\n};\n\n\n```
['C++']