讨论/题目交流/🏆 第 158 场力扣周赛/
🏆 第 158 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

分割平衡字符串
可以攻击国王的皇后
掷骰子模拟
最大相等频率

展开讨论
力扣 (LeetCode)发起于 2019-10-13
最近编辑于 2019-10-14

5224. 掷骰子模拟

原题链接

dp[i][j][k] 表示第 i 轮掷骰子掷出数字 jj 连续出现 k 次的组合数量。

那么有状态转移如下:

j 并非在连续出现时(即 k == 1 时):

// j 出现 1 次的组合数等于上一轮投出非数字 j 的所有情况和
dp[i][j][1] = sum(dp[i - 1][other != j][:])

j 连续出现 k(k > 1) 次时:

if k <= rollMax[j]:
    // 本轮投出连续出现 k 次数字 j 的情况数量等于:上一轮连续投掷出 k - 1 次 j 的情况数量
    dp[i][j][k] = dp[i - 1][j][k - 1]

ps:很多同学说测试用例是错的,可能是因为理解错题意了,题目说的是 连续 掷出数字 i 的次数不能超过 rollMax[i],而不是数字的投掷总数。

具体实现:

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[[0 for _ in range(16)] for _ in range(7)] for _ in range(n + 1)]
        mod = 10**9 + 7
                
        for i in range(1, n + 1):
            # 投掷的数
            for j in range(1, 7):
                # 第一次投掷
                if i == 1:
                    dp[i][j][1] = 1
                    continue
                
                # 数字 j 连续出现 k 次
                for k in range(2, rollMax[j - 1] + 1):
                    dp[i][j][k] = dp[i - 1][j][k - 1]
                    
                # 前一次投出的数不是 j
                s = 0
                for l in range(1, 7):
                    if l == j:
                        continue
                    for k in range(1, 16):
                        s += dp[i - 1][l][k]
                        s %= mod
                dp[i][j][1] = s
        
        res = 0
        for j in range(1, 7):
            for k in range(1, 16):
                # 求投掷 n 次时所有组合总和
                res += dp[n][j][k]
                res %= mod
                
        return res
2
展开全部 14 讨论