Easy C++ Beginner Friendly DP + Backtracking Solution
\n\n# Code\n\nclass Solution {\npublic:\n    vector<int> vis;\n    int dp[202][202];\n    int mod = 1000000007;\n    int recur(string &s, int i, int n,int idx){
\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> vis;\n    int dp[202][202];\n    int mod = 1000000007;\n    int recur(string &s, int i, int n,int idx){\n        if(idx==n-1){\n            return 1;\n        }\n        if(dp[idx][i]!=-1)\n            return dp[idx][i];\n        \n        int res = 0;\n        if(s[idx]==\'D\'){\n            for(int j=i-1;j>=0;j--){\n                if(vis[j])  continue;\n                vis[j] = 1;\n                res = (res + (recur(s,j,n,idx+1))%mod)%mod;\n                vis[j] = 0; \n            }\n        }\n        else{\n            for(int j=i+1;j<n;j++){\n                if(vis[j])  continue;\n                vis[j] = 1;\n                res = (res + (recur(s,j,n,idx+1))%mod)%mod;\n                vis[j] = 0;\n            }\n        }\n        return dp[idx][i] = res;\n    }\n\n    int numPermsDISequence(string s) {\n        int n = s.size()+1;\n        vis.resize(n,0);\n        for(int i=0;i<202;i++){\n            for(int j=0;j<202;j++){\n                dp[i][j] = -1;\n            }\n        }\n        int ans = 0;\n        for(int i=0;i<n;i++){\n            vis[i] = 1;\n            ans = (ans + (recur(s,i,n,0))%mod)%mod;\n            vis[i] = 0;\n        }\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Backtracking', 'C++']