2318. 不同骰子序列的数目

Difficulty

Hard

Tags

动态规划

URL

https://leetcode.cn/problems/number-of-distinct-roll-sequences/

Star

给你一个整数 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

通过次数1,212提交次数2,378

法 1 动态规划

思路

🏑

935. 骑士拨号器加强版。本题需要考虑相邻位置不能重复，所以需要减掉一部分！

题解


class Solution:
    def distinctSequences(self, n: int) -> int:
        dp = [[0 for _ in range(7)] for _ in range(n)]
        for i in range(7):
            dp[0][i] = 1
        dp[0][0] = 0
            
        for i in range(1, n):
            if i == 1:
                dp[i][1] = dp[i-1][2]+dp[i-1][3]+dp[i-1][4]+dp[i-1][5]+dp[i-1][6]
                dp[i][2] = dp[i-1][1]+dp[i-1][3]+dp[i-1][5]
                dp[i][3] = dp[i-1][1]+dp[i-1][2]+dp[i-1][4]+dp[i-1][5]
                dp[i][4] = dp[i-1][1]+dp[i-1][3]+dp[i-1][5]
                dp[i][5] = dp[i-1][1]+dp[i-1][2]+dp[i-1][3]+dp[i-1][4]+dp[i-1][6]
                dp[i][6] = dp[i-1][1]+dp[i-1][5]
            elif i == 2:
                dp[i][1] = dp[i-1][2]+dp[i-1][3]+dp[i-1][4]+dp[i-1][5]+dp[i-1][6]   -dp[i-2][1]*5
                dp[i][2] = dp[i-1][1]+dp[i-1][3]+dp[i-1][5]                         -dp[i-2][2]*3
                dp[i][3] = dp[i-1][1]+dp[i-1][2]+dp[i-1][4]+dp[i-1][5]              -dp[i-2][3]*4
                dp[i][4] = dp[i-1][1]+dp[i-1][3]+dp[i-1][5]                         -dp[i-2][4]*3
                dp[i][5] = dp[i-1][1]+dp[i-1][2]+dp[i-1][3]+dp[i-1][4]+dp[i-1][6]   -dp[i-2][5]*5
                dp[i][6] = dp[i-1][1]+dp[i-1][5]                                    -dp[i-2][6]*2
            else:
                dp[i][1] = dp[i-1][2]+dp[i-1][3]+dp[i-1][4]+dp[i-1][5]+dp[i-1][6]   -dp[i-2][1]*4
                dp[i][2] = dp[i-1][1]+dp[i-1][3]+dp[i-1][5]                         -dp[i-2][2]*2
                dp[i][3] = dp[i-1][1]+dp[i-1][2]+dp[i-1][4]+dp[i-1][5]              -dp[i-2][3]*3
                dp[i][4] = dp[i-1][1]+dp[i-1][3]+dp[i-1][5]                         -dp[i-2][4]*2
                dp[i][5] = dp[i-1][1]+dp[i-1][2]+dp[i-1][3]+dp[i-1][4]+dp[i-1][6]   -dp[i-2][5]*4
                dp[i][6] = dp[i-1][1]+dp[i-1][5]                                    -dp[i-2][6]*1
            dp[i] = [num % 1000000007 for num in dp[i]]

        return sum(dp[-1]) % 1000000007