python DP top down + backtracking
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def numPermsDISequence(self, s: str) -> int:\n        n = len(s) + 1\n    \n\n        visit = set()\n        @functools.lru_cache(None)\n        def dp(prev, j):\n           \n            if j == len(s):\n                return 1\n            ans = 0\n            if prev == -1:\n                for i in range(n):\n                    visit.add(i)\n                    ans += dp(i+1, 0)\n                    visit.remove(i)\n                return ans\n            if s[j] == "D":\n\n                    for i in range(prev-1):\n                        if i in visit:\n                            continue\n                        visit.add(i)\n                        ans += dp(i+1, j+1)\n                        visit.remove(i)\n            else:\n                for i in range(prev, n):\n                        if i in visit:\n                            continue\n                        visit.add(i)\n                        ans += dp(i+1, j+1)\n                        visit.remove(i)\n            return ans\n        \n        return dp(-1, 0) % (10**9 + 7)\n\n\n\n\n```
['Dynamic Programming', 'Backtracking', 'Python3']