Extremely simple, clear & fast, 20 lines, Runtime: 100%, Memory: 100%, O(n²)
Intuition & Approach\n Describe your first thoughts on how to solve this problem. \n\nInitially I struggled to find a good solution, calculating permutations is
# Intuition & Approach\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nInitially I struggled to find a good solution, calculating permutations is very expensive, and with a complicated condition it would be difficult to reuse previously calculated permutations if I also need to keep track of which numbers I have used.\n\nHowever, after realizing that (for our conditions) the range [1,7,19] would be logically equivalent to the range [0,1,2], the problem could be simplified a lot by normalized all numbers after each removal. If I remove the element \'i\', and the next value should be smaller (\'D\'), I can specify that I will allow usage of all numbers from [0 <= x <= i-1], and if the next value should be bigger (\'I\'), I can specify that I only allow [i <= x <= totalNumbers].\n\nThis allows us to write a very basic memoization solution with time complexity O(n\xB2), using the two keys idx (numbers used) and i (previous number used) in two different layouts (increasing and decreasing), idx & i are both capped by n (length of s), O(n\xB2 + n\xB2) => O(n\xB2)\n\n\n\n\n\n# Complexity\n- Time complexity: O(n\xB2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n\xB2)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\npublic class Solution {\n    public int NumPermsDISequence(string s)\n        => (int)NormalizedMemoization(s, 0, 0, s.Length, new Dictionary<(int,int,int), long>());\n\n    public long NormalizedMemoization(string s, int idx, int min, int max, Dictionary<(int,int,int), long> memoization) {\n        if (idx == s.Length)\n            return min <= max ? 1 : 0;\n\n        if (memoization.TryGetValue((idx,min,max), out var ways))\n            return ways;\n\n        for (int i = min; i <= max; i++) {\n            if (s[idx] == \'D\') {\n                ways += NormalizedMemoization(s, idx+1, 0, i-1, memoization);\n            } else {\n                ways += NormalizedMemoization(s, idx+1, i, s.Length - idx - 1, memoization);\n            }\n        }\n        ways %= 1_000_000_007;\n        memoization[(idx,min,max)] = ways;\n        return ways;\n    }\n}\n```
['Recursion', 'Memoization', 'C#']