C++ | Memoization solution
```\nclass Solution {\nprivate:\n    int n,mod=1000000000+7;\n    vector>mem;\n    int solve(string &s,int index,int prev,vector&seen){\n        if(index==n){\n
```\nclass Solution {\nprivate:\n    int n,mod=1000000000+7;\n    vector<vector<int>>mem;\n    int solve(string &s,int index,int prev,vector<bool>&seen){\n        if(index==n){\n            return 1;\n        } else if(mem[index][prev]!=-1){\n            return mem[index][prev];\n        } else {\n            int ans=0;\n            if(s[index]==\'D\'){\n                for(int i=0;i<prev;i++){\n                    if(!seen[i]){\n                        seen[i]=true;\n                        ans=(ans%mod+solve(s,index+1,i,seen)%mod)%mod;\n                        seen[i]=false;\n                    }\n                }\n            } else {\n                for(int i=prev+1;i<=n;i++){\n                    if(!seen[i]){\n                        seen[i]=true;\n                        ans=(ans%mod+solve(s,index+1,i,seen)%mod)%mod;\n                        seen[i]=false;\n                    }\n                }\n            }\n            return mem[index][prev]=ans;\n        }\n    }\npublic:\n    int numPermsDISequence(string &s) {\n        n=s.size();\n        int ans=0;\n        mem=vector<vector<int>>(n+1,vector<int>(n+1,-1));\n        vector<bool>seen(n+1,false);\n        for(int i=0;i<=n;i++){\n            seen[i]=true;\n            ans=(ans%mod+solve(s,0,i,seen)%mod)%mod;\n            seen[i]=false;\n        }\n        return ans;\n    }\n};
['Dynamic Programming', 'Memoization', 'C', 'C++']