Detailed explanation and intuition
Intuition\n\nThe possible lengths of s, and the fact that there\'s a modulo involved, hints that were dealing with some sort of recursive function.\n\nIndeed, w
# Intuition\n\nThe possible lengths of `s`, and the fact that there\'s a modulo involved, hints that were dealing with some sort of recursive function.\n\nIndeed, we have a very large number of alternatives for each step. For a 200 character string, there are 200 valid first choices to explore (some of which may later turn out to be invalid). Then, there\'s potentially 199 choices, and so on, yielding $\\textrm{O}(n!)$.\n\nThis tells us that we need to memoize each step somehow. For memoization to work, we must describe the state in such a way that the state space isn\'t too large.\n\nA naive first attempt at a state would be to store:\n\n1. $\\textrm{O}(n)$ - previously picked index\n2. $\\textrm{O}(n)$ - remaining string length\n3. $\\textrm{O}(n!)$ - set of remaining numbers\n\nClearly, (3) won\'t work.\n\nAt this point when you\'re stuck, it\'s good to write down some different examples and look for clues. Try moving from a massive `n` to the next step, like `n = 100` to `n = 99`. Try to move from `n = 1` to `n = 0`. Try the other direction, i.e. to introduce a new number to the set.\n\nFor me, the breakthrough was when I imagined the last step of a long series of changes that started with `n = 100`. What possible numbers could be left in the set?\n\n$$\n\\{ (0, 1), (0, 2), ..., (0, n) \\}\\\\\n\\{ (1, 0), (1, 2), ..., (1, n) \\}\\\\\n... \\\\\n\\{ (n, 0), (n, 1), ..., (n, n-1) \\}\\\\\n$$\n\nTo evaluate `\'D\'` or `\'I\'` with these pairs, it only mattered whether the pair was increasing or decreasing. In other words, we could reduce all these pairs to $(0, 1)$ or $(1, 0)$ and it would make no difference to the result.\n\nThis told me that the set could always contain the same numbers, i.e. from `0..n`. It was only the relative position of numbers that mattered.\n\n# Approach\n\nDue to the reasoning above, the set of possible choices is dependent only on the length of / position in `s` and the previously picked value `x`. This gives us a state space of $\\textrm{O}(n^2)$.\n\nOnce a valid current number is found, we pick it and continue evaluation. Since the set of numbers is reduced each turn, we must deduct 1 from number `y` when is larger than `x` (x is removed from the set).\n\nNote: it is trivial to change top-down to bottom-up, almost always at the expense of legibility. So I\'ll stick with top-down here.\n\n# Complexity\n\n- Time complexity: $\\textrm{O}(n^2)$\n- Space complexity: $\\textrm{O}(n^2)$\n\n# Code\n\n```go\nconst mod = 1e9 + 7\n\nfunc numPermsDISequence(s string) int {\n\tvar res int\n\tn := len(s)\n\tmem := make([][]int, n+1)\n\tfor i := range mem {\n\t\tmem[i] = make([]int, n+1)\n\t\tfor j := range mem[i] {\n\t\t\tmem[i][j] = -1\n\t\t}\n\t}\n\tfor i := 0; i <= n; i++ {\n\t\tres = (res + numPerms(mem, s, i)) % mod\n\t}\n\treturn res\n}\n\nfunc numPerms(mem [][]int, s string, x int) int {\n\tn := len(s)\n\tif mem[n][x] != -1 {\n\t\treturn mem[n][x]\n\t}\n\tif len(s) == 0 {\n\t\treturn 1\n\t}\n\tvar res int\n\tif s[0] == \'I\' {\n\t\tfor y := x + 1; y <= n; y++ {\n\t\t\tres = (res + numPerms(mem, s[1:], y-1)) % mod\n\t\t}\n\t} else {\n\t\tfor y := x - 1; y >= 0; y-- {\n\t\t\tres = (res + numPerms(mem, s[1:], y)) % mod\n\t\t}\n\t}\n\tmem[n][x] = res\n\treturn res\n}\n```
['Go']