Python recursive solution, detailed explanation
Intuition\nLooks like a DP problem, since sub problems are getting reused. \n\n# Approach\nWe just need to keep track of state of dp. i.e since we\'re only inte
# Intuition\nLooks like a DP problem, since sub problems are getting reused. \n\n# Approach\nWe just need to keep track of state of dp. i.e since we\'re only interested in number of solutions, the numbers itself dont matter only the number of elements above and below out previous choice.\n \nState = (idx, u, b) \nidx = index in s\nu = no elements above prev\nb = no elements below prev\n\n# Complexity\n- Time complexity:\n$$O(N^3)$$ : no of state = N^2, time per state = N\n(since a is redundant, a = n-idx-b, we actually have only N^2 states and a can be removed. only added for simplicity of explanation)\n\n- Space complexity:\n$$O(N^3)$$ : same as above\n\n# Code\n```\nclass Solution:\n    def numPermsDISequence(self, s: str) -> int:\n        """\n        1) brute force: all possible perms and check if valid => n+1!*n (too big) \n        2) dynamic programming: since if we are at an idx i, the rest of the substring is getting repeated.\n        state => (current idx of s, no. choices above prev, no. choices below prev)\n        transition => case1: \'D\' we can choose any element from above choices. \n                      case2: \'I\' we can choose any element from below choices.\n        """\n        n = len(s)\n        mod = 10**9+7\n        ans = 0 \n        @cache\n        def rec(idx, a, b):\n            # if it reaches end it means its a valid sequence (implicitly means a=0, b=0)\n            if idx == n: return 1   \n            # initialize valid sequences to 0 \n            ret = 0 \n            if s[idx] == \'D\':\n                # if current idx is D, then we choose any element from the \'b\' elements below it.\n                # correspondingly update a and b (elements above and below element we choose)\n                for i in range(1,b+1):\n                    ret+=rec(idx+1, a+i-1, b-i)\n            elif s[idx] == \'I\':\n                for i in range(1,a+1):\n                    ret+=rec(idx+1, a-i, b+i-1)\n            return ret%mod\n        # we take first element as any of the 0 to n. and find for all starting elements. \n        for i in range(n+1):\n            ans = (ans + rec(0, n-i, i))%mod\n        return ans\n```
['Python3']