C++ Easy Solution✅|Using DP & Backtraking🔥|Optimal Solution
\n\n# Complexity\n- Time complexity:O(NNN)\n\n- Space complexity:O(N*N)\n Add your space complexity here, e.g. O(n) \n\n# Code\n\nclass Solution {\npublic:\n   
\n\n# Complexity\n- Time complexity:O($$N*N*N$$)\n\n- Space complexity:O($$N*N$$)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int mod=1e9+7;\n    //TC=O(N*N*N)\n    //SC=O(N*N)\n    int find(int ind,int pre,string& s,int n,vector<bool>& vis,vector<vector<int>>& dp){\n        if(ind==n){\n            return 1;\n        }\n        if(dp[ind][pre+1]!=-1){\n            return dp[ind][pre+1];\n        }\n        int way1=0,way2=0;\n        if(pre==-1){\n            for(int i=0;i<=n;i++){\n                if(!vis[i]){\n                    vis[i]=true;\n                    way1=(way1+find(ind,i,s,n,vis,dp))%mod;\n                    vis[i]=false;\n                }\n            }\n            return way1%mod;\n        }\n        else{\n            if(s[ind]==\'D\'){\n                for(int i=0;i<=n;i++){\n                    if(i<pre){\n                        if(!vis[i]){\n                            vis[i]=true;\n                            way1=(way1+find(ind+1,i,s,n,vis,dp))%mod;\n                            vis[i]=false;\n                        }\n                    }\n                }\n            }else{\n                for(int i=0;i<=n;i++){\n                    if(i>pre){\n                        if(!vis[i]){\n                            vis[i]=true;\n                           \n                            way2=(way2+find(ind+1,i,s,n,vis,dp))%mod;\n                            vis[i]=false;\n                        }\n                    }\n\n                }\n            }\n        }\n        return dp[ind][pre+1]=(way1+way2)%mod;\n    }\n    int numPermsDISequence(string s) {\n        int n=s.size();\n        vector<vector<int>> dp(n+1,vector<int>(n+2,-1));\n        vector<bool> vis(n+1,false);\n        return find(0,-1,s,n,vis,dp);\n    }\n};\n```\n# AUTHOR:JAYESH BADGUJAR\n\n
['Dynamic Programming', 'Backtracking', 'Memoization', 'C++']