[Swift]LeetCode1223.掷骰子模拟|DiceRollSimulation

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（let_us_code）
➤博主域名：https://www.zengqiang.org
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

A die simulator generates a random number from 1 to 6 for each roll. You introduced a constraint to the generator such that it cannot roll the number i more than rollMax[i] (1-indexed) consecutive times.

Given an array of integers rollMax and an integer n, return the number of distinct sequences that can be obtained with exact n rolls.

Two sequences are considered different if at least one element differs from each other. Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: n = 2, rollMax = [1,1,2,2,2,3]
Output: 34
Explanation: There will be 2 rolls of die, if there are no constraints on the die, there are 6 * 6 = 36 possible combinations. In this case, looking at rollMax array, the numbers 1 and 2 appear at most once consecutively, therefore sequences (1,1) and (2,2) cannot occur, so the final answer is 36-2 = 34.
Example 2:

Input: n = 2, rollMax = [1,1,1,1,1,1]
Output: 30
Example 3:

Input: n = 3, rollMax = [1,1,1,2,2,3]
Output: 181

Constraints:

1 <= n <= 5000
rollMax.length == 6
1 <= rollMax[i] <= 15

有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。

不过我们在使用它时有个约束，就是使得投掷骰子时，连续掷出数字 i 的次数不能超过 rollMax[i]（i 从 1 开始编号）。

现在，给你一个整数数组 rollMax 和一个整数 n，请你来计算掷 n 次骰子可得到的不同点数序列的数量。

假如两个序列中至少存在一个元素不同，就认为这两个序列是不同的。由于答案可能很大，所以请返回模 10^9 + 7 之后的结果。

示例 1：

输入：n = 2, rollMax = [1,1,2,2,2,3]
输出：34
解释：我们掷 2 次骰子，如果没有约束的话，共有 6 * 6 = 36 种可能的组合。但是根据 rollMax 数组，数字 1 和 2 最多连续出现一次，所以不会出现序列 (1,1) 和 (2,2)。因此，最终答案是 36-2 = 34。
示例 2：

输入：n = 2, rollMax = [1,1,1,1,1,1]
输出：30
示例 3：

输入：n = 3, rollMax = [1,1,1,2,2,3]
输出：181

提示：

1 <= n <= 5000
rollMax.length == 6
1 <= rollMax[i] <= 15

Runtime: 20 ms

Memory Usage: 21.6 MB

 1 class Solution {
 2     func dieSimulator(_ n: Int, _ rollMax: [Int]) -> Int {
 3         let divisor:Int = 1000000007
 4         var dp:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:7),count:n)
 5         for i in 0..<6
 6         {
 7             dp[0][i] = 1
 8         }
 9         dp[0][6] = 6
10         for i in 1..<n
11         {
12             var sum:Int = 0
13             for j in 0..<6
14             {
15                 dp[i][j] = dp[i - 1][6]
16                 if i - rollMax[j] < 0
17                 {
18                     sum = (sum + dp[i][j]) % divisor
19                 }
20                 else
21                 {
22                     if i - rollMax[j] - 1 >= 0
23                     {
24                         dp[i][j] = (dp[i][j] - (dp[i - rollMax[j] - 1][6] - dp[i - rollMax[j] - 1][j])) % divisor + divisor
25                     }
26                     else
27                     {
28                         dp[i][j] = (dp[i][j] - 1) % divisor
29                     }
30                     sum = (sum + dp[i][j]) % divisor
31                 }
32             }
33             dp[i][6] = sum
34         }
35         return dp[n - 1][6]
36     }
37 }

340ms

 1 class Solution {
 2     func dieSimulator(_ n: Int, _ rollMax: [Int]) -> Int {
 3                 
 4         let MOD = 1000_000_007
 5         let SIDES = 6
 6         let MAX_ROLLS = 15
 7         let STATES = SIDES * MAX_ROLLS
 8 
 9         var dp = [Int](repeating: 0, count: STATES)
10 
11         for side in 0..<6 {
12             dp[side] = 1
13         }
14 
15         for i in 0..<n-1 {
16             var next_dp = [Int](repeating: 0, count: STATES)
17             for state in 0..<STATES {
18                 let rolls = state / SIDES + 1
19                 let side = state % SIDES
20                 for die in 0..<6 {
21                     let new_rolls = side == die ? rolls + 1 : 1
22                     if new_rolls > rollMax[die] {
23                         continue
24                     }
25                     next_dp[(new_rolls - 1) * SIDES + die] += dp[state]
26                 }
27             }
28             for s in 0..<STATES {
29                 next_dp[s] %= MOD
30             }
31             dp = next_dp
32         }
33         return dp.reduce(0, +)%MOD
34     }
35 }

796ms

 1 class Solution {
 2     func dieSimulator(_ n1: Int, _ rollMax: [Int]) -> Int {
 3         let MOD = 1000_000_007
 4 
 5         var memo = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: 0, count: 6), count: 16), count: 5001)
 6 
 7         func dfs(_ n: Int, _ k: Int, _ idx: Int) -> Int {
 8             if n == 0 {
 9                 return 1
10             }
11 
12             if memo[n][k][idx] != 0 {
13                 return memo[n][k][idx]
14             }
15 
16             var v = 0
17             for i in 0..<6 {
18                 if i != idx {
19                     v += dfs(n-1, 1, i)%MOD
20                 } else {
21                     if k < rollMax[i] {
22                         v += dfs(n-1, k+1, i)%MOD
23                     }
24                 }
25             }
26             memo[n][k][idx] = v%MOD
27             return v
28         }
29 
30         var ans = 0
31         for i in 0..<6 {
32             ans += dfs(n1-1, 1, i)%MOD
33         }
34         return ans%MOD
35     }
36 }