动态规划-线性dp-三维dp-6107. 不同骰子序列的数目

2022-06-26 11:38:29

问题描述：

给你一个整数 n 。你需要掷一个 6 面的骰子 n 次。请你在满足以下要求的前提下，求出 不同 骰子序列的数目：

1. 序列中任意 相邻 数字的 最大公约数 为 1 。
2. 序列中 相等 的值之间，至少有 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 <= 10e4 

问题求解：

自然的可以想到动态规划，难点在于间隔值如何去除，若采用二维dp问题没有办法高效解决，因此可以考虑三维dp。

class Solution:
    def distinctSequences(self, n: int) -> int:
        if n == 1: return 6
        
        mod = int(1e9) + 7
        
        def gcd(i, j):
            return gcd(j, i % j) if j else i
        
        dp = [[[0] * 7 for _ in range(7)] for _ in range(n + 1)]
        for i in range(1, 7):
            for j in range(1, 7):
                if gcd(i, j) == 1 and i != j:
                    dp[2][i][j] = 1
        
        for i in range(3, n + 1):
            for j in range(1, 7):
                for k in range(1, 7):
                    if gcd(j, k) == 1 and j != k:
                        for t in range(1, 7):
                            if t != j:
                                dp[i][j][k] = (dp[i][j][k] + dp[i - 1][k][t]) % mod
        
        res = 0
        for i in range(1, 7):
            for j in range(1, 7):
                res = (res + dp[n][i][j]) % mod
        return res