C++ || Bactracking || Memoization
Intuition\n Describe your first thoughts on how to solve this problem. \nWe need to explore all possible combinations to get the total count of valid permutatio
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe need to explore all possible combinations to get the total count of valid permutations\nFor this we only need previous element and current index to decide current element\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)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nconst int mod = 1e9+7;\nclass Solution {\n    int n, vis[202], dp[202][202];\nprivate:\n    int f(int prev, int len, string& s){\n        if(len == n+1) return 1;\n        if(dp[prev+1][len] != -1) return dp[prev+1][len];\n        int ans = 0;\n        if(prev == -1){\n            for(int i=0; i<=n; i++){\n                vis[i] = 1;\n                ans = (ans + f(i,len+1,s))%mod;\n                vis[i] = 0;\n            }\n        }\n        else if(prev != -1 && s[len-1] == \'D\'){\n            for(int i=0; i<prev; i++){\n                if(!vis[i]){\n                    vis[i] = 1;\n                    ans = (ans + f(i,len+1,s))%mod;\n                    vis[i] = 0;\n                }\n            }\n        }\n        else if(prev != -1 && s[len-1] == \'I\'){\n            for(int i=prev+1; i<=n; i++){\n                if(!vis[i]){\n                    vis[i] = 1;\n                    ans = (ans + f(i,len+1,s))%mod;\n                    vis[i] = 0;\n                }\n            }\n        }\n\n        return dp[prev+1][len] = ans;\n    }\npublic:\n    int numPermsDISequence(string s) {\n        n = s.size();\n        memset(vis, 0, sizeof(vis));\n        memset(dp, -1, sizeof(dp));\n        return f(-1,0,s);\n    }\n};\n```
['C++']