EASY C++ SOLUTION DP | RECURSION | MEMOIZATION
\nclass Solution {\npublic:\n    \n    int dp[201][201];\n    int m = 1e9+7;\n    int helper(string &s, int i, vector<bool> &visit, int start){\n        if(i==s
```\nclass Solution {\npublic:\n    \n    int dp[201][201];\n    int m = 1e9+7;\n    int helper(string &s, int i, vector<bool> &visit, int start){\n        if(i==s.length()){\n            return 1;\n        }\n        \n        if(dp[i][start]!=-1){\n            return dp[i][start];\n        }\n        if(s[i]==\'D\'){\n            int ans = 0;\n            for(int j = 0;j < start;j++){\n            \n                if(visit[j]==false){\n                    visit[j]=true;\n                    ans = (ans%m + helper(s,i+1,visit,j)%m)%m;\n                    visit[j]=false;\n                }\n            }\n            return dp[i][start] = ans;\n        }\n        else{\n            int ans = 0;\n            for(int j = start+1;j <= s.length();j++){\n            \n                if(visit[j]==false){\n                    visit[j]=true;\n                    ans = (ans%m + helper(s,i+1,visit,j)%m)%m;\n                    visit[j]=false;\n                }\n            }\n            return dp[i][start] = ans;\n        }\n    }\n    \n    \n    int numPermsDISequence(string s) {\n        vector<bool> visit(s.length()+1,false);\n        int ans = 0;\n             memset(dp,-1,sizeof(dp));\n        for(int i = 0; i <= s.length();i++){\n            visit[i]=true;\n       \n            ans = (ans%m + helper(s,0,visit,i)%m)%m;\n            visit[i]=false;\n        }\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C', 'C++']