LeetCode 题解工作台
不同骰子序列的数目
给你一个整数 n 。你需要掷一个 6 面的骰子 n 次。请你在满足以下要求的前提下，求出 不同 骰子序列的数目： 序列中任意 相邻 数字的 最大公约数 为 1 。 序列中 相等 的值之间，至少有 2 个其他值的数字。正式地，如果第 i 次掷骰子的值 等于 第 j 次的值，那么 abs(i - j) …
2
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
三维 DP。 设 表示序列长度为 ，且序列的最后两个数字分别为 , 的所有满足要求的不同序列的数量。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数 n 。你需要掷一个 6 面的骰子 n 次。请你在满足以下要求的前提下，求出 不同 骰子序列的数目：
- 序列中任意 相邻 数字的 最大公约数 为
1。 - 序列中 相等 的值之间，至少有
2个其他值的数字。正式地，如果第i次掷骰子的值 等于 第j次的值，那么abs(i - j) > 2。
请你返回不同序列的 总数目 。由于答案可能很大，请你将答案对 109 + 7 取余 后返回。
如果两个序列中至少有一个元素不同，那么它们被视为不同的序列。
示例 1：
输入：n = 4 输出：184 解释：一些可行的序列为 (1, 2, 3, 4) ，(6, 1, 2, 3) ，(1, 2, 3, 1) 等等。 一些不可行的序列为 (1, 2, 1, 3) ，(1, 2, 3, 6) 。 (1, 2, 1, 3) 是不可行的，因为第一个和第三个骰子值相等且 abs(1 - 3) = 2 （下标从 1 开始表示）。 (1, 2, 3, 6) i是不可行的，因为 3 和 6 的最大公约数是 3 。 总共有 184 个不同的可行序列，所以我们返回 184 。
示例 2：
输入：n = 2 输出：22 解释：一些可行的序列为 (1, 2) ，(2, 1) ，(3, 2) 。 一些不可行的序列为 (3, 6) ，(2, 4) ，因为最大公约数不为 1 。 总共有 22 个不同的可行序列，所以我们返回 22 。
提示：
1 <= n <= 104
解题思路
方法一：动态规划
三维 DP。
设 表示序列长度为 ，且序列的最后两个数字分别为 , 的所有满足要求的不同序列的数量。
class Solution:
def distinctSequences(self, n: int) -> int:
if n == 1:
return 6
mod = 10**9 + 7
dp = [[[0] * 6 for _ in range(6)] for _ in range(n + 1)]
for i in range(6):
for j in range(6):
if gcd(i + 1, j + 1) == 1 and i != j:
dp[2][i][j] = 1
for k in range(3, n + 1):
for i in range(6):
for j in range(6):
if gcd(i + 1, j + 1) == 1 and i != j:
for h in range(6):
if gcd(h + 1, i + 1) == 1 and h != i and h != j:
dp[k][i][j] += dp[k - 1][h][i]
ans = 0
for i in range(6):
for j in range(6):
ans += dp[-1][i][j]
return ans % mod
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for an understanding of dynamic programming and state transitions.
- question_mark
Check if the candidate correctly identifies the GCD condition and its impact on sequence validity.
- question_mark
Evaluate if the candidate is able to optimize the solution using modulo 10^9 + 7.
常见陷阱
外企场景- error
Forgetting to handle the GCD condition correctly, resulting in incorrect valid sequences.
- error
Failing to use dynamic programming efficiently, leading to excessive time complexity.
- error
Not applying modulo 10^9 + 7 consistently, leading to integer overflow or incorrect answers.
进阶变体
外企场景- arrow_right_alt
Use memoization to optimize the dynamic programming solution.
- arrow_right_alt
Extend the problem to consider rolling a die with more than six sides.
- arrow_right_alt
Consider optimizing space by reducing the state storage for previous rolls.