Dynamic Programming O(n^3) Time Complexity
Intuition\n- We can solve this using Dynamic Programming\n- we need to fix valid elements and at the need to check whether we can form a valid permutation or no
# Intuition\n- We can solve this using Dynamic Programming\n- we need to fix valid elements and at the need to check whether we can form a valid permutation or not \n- if we can then add 1 and check for remaining combinations\n\n# Complexity\n- Time complexity: $$O(n^3)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n^2)$$ for dp\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int MOD = 1e9+7;\n    long long dp[202][202];\n    long long perms(string &s, int n, int pos, int prev, vector<bool> &visited) {\n        if(pos >= n) return 1; // if you can reach till end then you have found one valid permutation\n        if(dp[pos][prev] != -1) return dp[pos][prev];\n        long long ans = 0;\n        //we have to fix rest elements in permutation so we need to check all elements for next position\n        for(int i=0;i<=n;i++) {\n            //if it not visited\n            if(!visited[i]) {\n                //check whether current element satisfies these conditions\n                if(s[pos] == \'D\' && prev > i) {\n                    visited[i] = true;\n                    //then consider it and go for next position and current will become previous\n                    ans = (ans + perms(s,n,pos+1,i,visited) % MOD) % MOD;\n\n                    //will backtracking make sure to revoke changes\n                    visited[i] = false;\n                }\n                if(s[pos] == \'I\' && prev < i) {\n                    visited[i] = true;\n                    ans = (ans + perms(s,n,pos+1,i,visited) % MOD) % MOD;\n                    visited[i] = false;\n                }\n            }\n        }\n        return dp[pos][prev] = ans;\n    }\n    int numPermsDISequence(string s) {\n        int n = s.length();\n        long long ans = 0;\n        memset(dp,-1,sizeof(dp));\n        //we need to fix the starting element in permutation and check how many \n        //combinations are satisfied\n        for(int i=0;i<=n;i++) {\n\n            //visited array to keep track of not considering the element in permutation if it is\n            //previously visited\n            vector<bool> visited(n+1,false);\n            visited[i] = true;\n            //we need to consider pos and prev variables\n            //pos to keep track of string s\n            //prev to keep track of previously considered element\n            ans = (ans + perms(s,n,0,i,visited) % MOD) % MOD;\n        }\n        return ans;\n    }\n};\n```
['C++']