PYTHON | RECURSION + MEMOIZATION | FULL EXPLANATION | EASY | DP |
EXPLANATION\nThis problem can be easily solved with recursion where \n\nIn every recursive call we choose the next element of sequence until we reach the length
# EXPLANATION\nThis problem can be easily solved with recursion where \n\nIn every recursive call we choose the next element of sequence until we reach the length of sequence\n\nSO every recursive call we have a choice to make the next element from [ 1, 2, 3, 4, 5, 6] \nwith the condition that last element can only be repeated for maximum rollMax[i-1] times\n\nSo we have to check this condition as well , to do so we can keep track of sequence of last item . \n\nBase case will be when n == 0 : we should return 1 denoting that we got an unique sequence\n\nNOW if we observe from a point we can have multiple recursions hence this gives the idea of DP\n\nNow the best way to solve the problem with multiple recursive calls is top down DP\n\nWe memoize the variables which are changing in each recursive call and store the answer\nfor that particular problem in our dictionary \n\nHere  n , last_element , count are changing in each recursive calls so we store them in dp\n# CODE\n```\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = {}\n        def solve(n,last,count):\n            if n == 0: return 1\n            if (n,last,count) in dp: return dp[(n,last,count)]\n            ans = 0\n            for i in range(6):\n                if last == i:\n                    if count == rollMax[i]: continue\n                    ans += solve(n-1,last,count + 1)\n                else:\n                    ans += solve(n-1,i,1)\n            dp[(n,last,count)] = ans\n            return ans\n        \n        return solve(n,None,0) % 1000000007\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Python', 'Python3']