C++ | DFS + MEMO
\nclass Solution {\npublic:\n    int mod = 1e9+7;\n    int dfs(vector<vector<int>> &dp,vector<bool> &vis,string &s,int in,int n,int last){\n        if(in>=s.siz
```\nclass Solution {\npublic:\n    int mod = 1e9+7;\n    int dfs(vector<vector<int>> &dp,vector<bool> &vis,string &s,int in,int n,int last){\n        if(in>=s.size()) return 1;\n        if(dp[in][last]!=-1) return dp[in][last];\n        if(s[in]==\'D\'){  \n            long re = 0;\n            for(int i = 0; i<last; ++i){\n                if(vis[i]==1) continue;\n                vis[i] = 1;\n                int k = dfs(dp,vis,s,in+1,n,i);\n                vis[i]=0;\n                re = (re + k)%mod;\n            }\n            return dp[in][last] = (int)re;\n        }\n        else{\n            long re = 0;\n            for(int i = last+1; i<=s.size(); ++i){\n                if(vis[i]==1) continue;\n                vis[i] = 1;\n                int k = dfs(dp,vis,s,in+1,n,i);\n                vis[i]=0;\n                re = (re + k)%mod;\n            }\n            return dp[in][last] = (int)re;\n        }\n    }\n    int numPermsDISequence(string s) {\n        int n = s.size(), i = 0; \n        long re = 0;\n        vector<vector<int>> dp(n+2,vector<int>(n+2,-1));\n        vector<bool> vis(n+1,0);\n        \n        if(s[0]==\'D\') i++; \n        for(;i<=n;i++){\n            vis[i] = 1;\n            re = (re + dfs(dp,vis,s,0,n,i))%mod;\n            vis[i] = 0;\n        }\n        return (int)re;\n    }\n};\n```
['Dynamic Programming', 'C']