[Python3] DP & Slide windows, beats 100% time & 100% space
136 ms & 13.9MB. Faster & memory less than 100% Python3 submissions.\nBesides regular DP solutions, I noticed that all we only need to maintain is a sliding win
136 ms & 13.9MB. Faster & memory less than 100% Python3 submissions.\nBesides regular DP solutions, I noticed that all we only need to maintain is a sliding window for each i (1-6). And its length should be this number\'s maximum limit. For example, if rollMax = [2,1,1,3,3,2], then for number 1, the DP cache\'s length should be rollMax[0] = 2. Similarly, the DP cache should look like this initially:\n[\n\t[0, 0],\n\t[0],\n\t[0],\n\t[0, 0, 0],\n\t[0, 0, 0],\n\t[0, 0]\n].\nAnd for cache i with the length rollMax[i-1], its last j-th digit dp[i][-j] represents how many combinations ending with j times i consecutively. For example, if n=4, rollMax = [2,1,1,3,3,2], then the final DP cache is:\n[\n\t[28, 159], # 28 * "--11", 159 * "---1" \n\t[163],\n\t[163],\n\t[5, 28, 158], # 5 * "-444", 28 * "--44", 158 * "---4"\n\t[5, 28, 158],\n\t[28, 159]\n],\nThe final result is the sum of these values. Updating these windows is easy. Each time we just left shift the window, and the new window[i][-1], which represents how many strings ending with just 1 i, should be the sum of other 5 numbers. Here is the code with comments:\n```\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mod = 10 ** 9 + 7\n        window = [[0] * i for i in rollMax] # DP cache\n        for i in range(6):\n            window[i][-1] = 1 # n=1\n        for _ in range(2, n + 1):\n            sumL = [sum(i) % mod for i in window]\n            sum_sum = sum(sumL) % mod\n            for i in range(6):\n                window[i][:-1] = window[i][1:] # left shift\n                window[i][-1] = sum_sum - sumL[i] # new win[i][-1]: the sum of the other 5 numbers\n        return sum([sum(i) % mod for i in window]) % mod\n```\nI think this solution is pretty elegant and straightforward, for it can save lots of unnecessary space. Welcome any comments.\n
['Dynamic Programming', 'Sliding Window']