[Python] Simple memoization
I am trying to understand the multidimensional DP solution, but meanwhile I tried to solve the problem recursively. Following is the code - \n\n\ndef helper(cur
I am trying to understand the multidimensional DP solution, but meanwhile I tried to solve the problem recursively. Following is the code - \n```\n\ndef helper(currentIndex, n, rollMax, pre):\n    if currentIndex==n:\n        return 1\n    elif currentIndex>n:\n        return 0\n    count = 0\n    for index in xrange(6):    # the die can currently turn to all the faces\n        if index!=pre: #it cannot turn to the face which has occured just previously\n            for repeat in xrange(1,rollMax[index]+1): #can roll till max. consecutive rolls allowed for this face\n                count+=helper(currentIndex+repeat,n,rollMax,index)\n    return count\n\nclass Solution(object):\n    def dieSimulator(self, n, rollMax):\n        """\n        :type n: int\n        :type rollMax: List[int]\n        :rtype: int\n        """\n        MOD = 10**7+7\n        return helper(0,n,rollMax,-1)%MOD\n```\n\t\t\nIt timed out on the following test case - \n10\n[2,7,1,2,6,5]\n\nI added memoization and submitted the following code - \n```\ndef helper(currentIndex, n, rollMax, pre,d):\n    if currentIndex==n:\n        return 1\n    elif currentIndex>n:\n        return 0\n    count = 0\n    if (currentIndex,pre) in d: #if this state is already calculated, return the ans\n        return d[(currentIndex,pre)]\n    for index in xrange(6):\n        if index!=pre:\n            for repeat in xrange(1,rollMax[index]+1):\n                count+=helper(currentIndex+repeat,n,rollMax,index,d)\n    d[(currentIndex,pre)]=count   #save the computation\n    return count\n\nclass Solution(object):\n    def dieSimulator(self, n, rollMax):\n        """\n        :type n: int\n        :type rollMax: List[int]\n        :rtype: int\n        """\n        rolledCount = [0]*6  #no rolls made yet\n        MOD = 10**9+7\n        d = {}  #dictionary to save the states\n        return helper(0,n,rollMax,-1,d)%MOD\n```\n\nAnd it passed all the test cases !!!
['Memoization', 'Python']