C++ | Memoization | Backtracking | Easy
\nclass Solution {\npublic:\n    int vis[201];\n    long long int dp[202][202];\n    int mod=1000000007;\n    int util(string &s,int index,int prev){\n        i
```\nclass Solution {\npublic:\n    int vis[201];\n    long long int dp[202][202];\n    int mod=1000000007;\n    int util(string &s,int index,int prev){\n        if(index==s.size()) return 1;\n        \n        if(dp[index][prev]!=-1) return dp[index][prev];\n        \n        long long int cnt=0;\n        if(s[index]==\'D\'){\n           for(int i=0;i<prev;i++){\n               if(vis[i]==0){\n                    vis[i]=1;\n                    cnt+=(util(s,index+1,i))%mod;\n                     vis[i]=0;\n               }\n           } \n        }\n        else{\n            for(int i=prev+1;i<=s.size();i++){\n                if(vis[i]==0){\n                    vis[i]=1;\n                    cnt+=(util(s,index+1,i))%mod;\n                    vis[i]=0;\n                }\n            }\n        }\n        return dp[index][prev]=cnt%mod;\n    }\n    int numPermsDISequence(string s) {\n        long long int cnt=0;\n         memset(vis,0,sizeof(vis));\n        memset(dp,-1,sizeof(dp));\n        for(int i=0;i<=s.size();i++){\n            vis[i]=1;\n            cnt+=(util(s,0,i))%mod;\n            vis[i]=0;\n        }\n        return cnt%mod;\n    }\n};\n```
['Dynamic Programming', 'Backtracking', 'Memoization', 'C']