Python O(N) Bottom Up DP with explaination
Denote dp[i][j][k] the number of possible combinations after 1+ith ( i from 0 to n-1) roll ending with 1+k consective digit 1+j ( j from 0 to 5).\n\nThen, for e
Denote `dp[i][j][k]` the number of possible combinations after `1+ith` ( `i` from 0 to n-1) roll ending with `1+k` consective digit `1+j` ( `j` from 0 to 5).\n\nThen, for every `k > 0`  (have 1+k consective same digits at the end), we have\n`dp[i][j][k] = dp[i-1][j][k-1] ==> k < rollMax[j]`\n\nFor `k == 0`, which means we only have one consective digit at the end, we have\n`dp[i][j][0] = sum( dp[i-1][t][k] )  ==>   t from 0 to 5 and t != j, k from 0 to rollMax[t]`\n\nThe base case, \n`dp[0][j][0] = 1 ==> j from 0 to 5`\n\nTIme complexity,\n`O(N*6*6*15) = O(N)`\n\nSpace complexity,\n`O(N*6*15) = O(N)`\n\nNote, we could optimize the space to O(1). However, the code is more intuitive without space optimization.\n\n```python\ndef dieSimulatorDP(self, n, rollMax):\n    K = max(rollMax)\n    dp = [[[0 for k in xrange(K)] for j in xrange(6)] for i in xrange(n)] \n    for j in xrange(6): dp[0][j][0] = 1\n    for i in xrange(1, n):\n        for j in xrange(6):\n            dp[i][j][0] += sum(dp[i-1][t][k] for t in xrange(6) for k in xrange(rollMax[t]) if t != j)\n            for k in xrange(1, rollMax[j]):\n                dp[i][j][k] = dp[i-1][j][k-1]\n    return sum(dp[n-1][j][k] for j in xrange(6) for k in xrange(K)) % (10**9+7)\n```
[]