DP Solution
To add a new character to a sequence we only have to consider the last element-\n\nLets say currently DID sequence is 1032- this can form\n\nDIDI - in cases whe
To add a new character to a sequence we only have to consider the last element-\n\nLets say currently DID sequence is 1032- this can form\n\nDIDI - in cases where we end with 3,4\nDIDD - in cases where we end with 0,1,2\n\nSo just use the last element value to create a new sequence.\n\n```\nclass Solution:\n    def numPermsDISequence(self, s: str) -> int:\n        mem=defaultdict(int)\n        def dfs(i,val=0):\n            if i==len(s):\n                return 1\n            if (i,val) in mem:\n                return mem[i,val]\n            p=0\n            if s[i]=="D":\n                for ind in range(0,val+1):\n                    p+=dfs(i+1,ind)%(10**9+7)\n            else:\n                for ind in range(val+1,i+2):\n                    p+=dfs(i+1,ind)%(10**9+7)\n            mem[i,val]=p\n            return p\n        return dfs(0)\n ```\n\t\t\t\t
['Python3']