1223. Dice Roll Simulation

way 1, plain DP 的写法.

今日所学:
DP 递推等式的左边. 递推结果(即当前问题)的维度数值可以出现常数, 不一定非要是 i, j 循环变量.
当前问题的状态含有常数, 拆解为(多个)子问题.

习得一个新模式, 即所谓的套路.
i.e.: for pre in (1..6): f[i][j][1] += f[i-1][pre][k]

状态定义为 f(k, index, i)，代表数字 index 在前面出现 k 次时，掷到 i 次骰子会出现的序列个数.

情况二：随机出的数字 curt_index 与 pre_index 不等，那么得到新的状态 f(1, curt_index, i), 当前问题, 状态含有常数 1, 连续一次.
情况三：随机出连续相同数字, curt_index == pre_index，还没到达上限，得到新状态 f(k+1, index, i)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        f = [[[0] * (16) for _ in range(6)] for _ in range(n + 1)]
        MOD = 10**9 + 7
        for j in range(6):
            f[1][j][1] = 1

        for i in range(2, n + 1):
            for j in range(6):
                for pre in range(6):
                    for k in range(1, rollMax[pre] + 1):
                        if pre != j:
                            f[i][j][1] += f[i-1][pre][k]
                        elif k < rollMax[j]:
                            f[i][j][k + 1] += f[i-1][j][k]

        ans = 0
        for j in range(6):
            for k in range(1, rollMax[j] + 1):
                ans = (ans + f[n][j][k]) % MOD

        return ans

way 2, DFS + memo: top down approach.

class Solution:
    def dieSimulator(self, n, rollMax):
        memo = {}
        self.MOD = 10**9 + 7
        memo = [[[-1] * 16 for _ in range(6)] for _ in range(n + 1)]
        ans = self.dfs(n, -1, 0, rollMax, memo)
        return ans

    def dfs(self, n, j, k, M, memo):
        if memo[n][j][k] != -1:
            return memo[n][j][k]
        if n == 0:
            return 1
        ans = 0
        for pre in range(6):
            if pre != j:
                ans += self.dfs(n - 1, pre, 1, M, memo)
            elif k < M[j]:
                ans += self.dfs(n - 1, pre, k + 1, M, memo)
        ans = ans % self.MOD
        memo[n][j][k] = ans
        return ans


o = Solution()

n = 2; rollMax = [1,1,2,2,2,3] # 34
# n = 3; rollMax = [1,1,1,2,2,3] # 181
ans = o.dieSimulator(n, rollMax)
print(ans)
n = 4; rollMax = [2,1,1,3,3,2] # 1082
ans = o.dieSimulator(n, rollMax)
print(ans)