DP

1223. Dice Roll Simulation

https://leetcode.com/problems/dice-roll-simulation/

Naive DP

This AC DP has the time complexity of (O(N*6*15)). As maximum N is 5000, the complexity will be 5000*6*15

Space complexity is O(15*6)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0]*15 for _ in range(6)]
        for k in range(6):dp[k][0]=1
        for i in range(n-1):
            #print("******",i)
            new_dp = [[0]*15 for _ in range(6)]
            for k in range(6):
                for pre_k in range(6):
                    if pre_k==k:
                        for m in range(15):
                            if m+1+1>rollMax[k]:break
                            new_m = m+1 
                            new_dp[k][m+1] += dp[k][m]
                    else:
                        for m in range(15):
                            new_dp[k][0] += dp[pre_k][m]
            # print(new_dp)
            dp = copy.deepcopy(new_dp)
            #for c in dp:print(c)
        return sum(sum(res) for res in dp) % (10**9+7)

The code below can make it a little bit faster.

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        S = max(rollMax)
        dp = [[0]*S for _ in range(6)]
        for k in range(6):dp[k][0]=1
        for i in range(n-1):
            new_dp = [[0]*S for _ in range(6)]
            dp_sum = sum(sum(dd) for dd in dp)
            for k in range(6):
                new_dp[k][1:rollMax[k]] = dp[k][:rollMax[k]-1]
                new_dp[k][0] = dp_sum - (sum(dp[k]))
            dp = copy.deepcopy(new_dp)
        return sum(sum(res) for res in dp) % (10**9+7)