Hard

题目描述

给你一个整数 n。你掷一个公平的 6 面骰子 n 次。确定满足以下条件的不同掷骰子序列的总数：

  1. 序列中任意相邻值的最大公约数等于 1。
  2. 相同数值的掷骰子之间至少间隔 2 次掷骰子。更正式地说，如果第 i 次掷骰子的值等于第 j 次掷骰子的值，那么 abs(i - j) > 2。

返回不同序列的总数。由于答案可能很大，请返回对 10^9 + 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（i 和 j 是从 1 开始索引的）。
(1, 2, 3, 6) 无效，因为 3 和 6 的最大公约数 = 3。
总共有 184 种不同的序列，所以返回 184。

示例 2：

输入：n = 2
输出：22
解释：一些可能的序列是 (1, 2), (2, 1), (3, 2)。
一些无效的序列是 (3, 6), (2, 4)，因为它们的最大公约数不等于 1。
总共有 22 种不同的序列，所以返回 22。

约束：

  • 1 <= n <= 10^4

解题思路

这道题是一个经典的动态规划问题，需要考虑状态设计和转移。

状态设计： 由于相同数值间需要至少间隔2次，我们需要记录前两次的掷骰子结果。定义 dp[i][j][k] 表示到第 i 次掷骰子，倒数第二次是 j，最后一次是 k 的方案数。

约束分析：

  1. 相邻数字的最大公约数为1：需要预处理哪些数字对互质
  2. 相同数值间隔至少2次：当前数字不能与前一次相同，但可以与前两次相同

转移方程： 对于第 i 次掷骰子选择数字 next：

  • next 与 k（上一次）互质
  • next 不等于 k（不能连续相同）
  • 可以等于 j（与前两次相同是允许的）

边界条件：

  • n = 1 时，答案是 6（任意数字都可以）
  • n = 2 时，只需考虑互质条件

优化： 可以预处理互质关系，避免重复计算最大公约数。

代码实现

class Solution {
public:
    int distinctSequences(int n) {
        if (n == 1) return 6;
        
        const int MOD = 1e9 + 7;
        
        // 预处理互质关系
        bool coprime[7][7] = {false};
        for (int i = 1; i <= 6; i++) {
            for (int j = 1; j <= 6; j++) {
                coprime[i][j] = (__gcd(i, j) == 1);
            }
        }
        
        // dp[i][j][k] 表示第i次掷骰子，前一次是j，当前是k的方案数
        vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(7, vector<long long>(7, 0)));
        
        // 初始化前两次掷骰子
        for (int j = 1; j <= 6; j++) {
            for (int k = 1; k <= 6; k++) {
                if (coprime[j][k] && j != k) {
                    dp[2][j][k] = 1;
                }
            }
        }
        
        // 填充dp表
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= 6; j++) {
                for (int k = 1; k <= 6; k++) {
                    for (int next = 1; next <= 6; next++) {
                        if (coprime[k][next] && k != next) {
                            dp[i][k][next] = (dp[i][k][next] + dp[i-1][j][k]) % MOD;
                        }
                    }
                }
            }
        }
        
        long long result = 0;
        for (int j = 1; j <= 6; j++) {
            for (int k = 1; k <= 6; k++) {
                result = (result + dp[n][j][k]) % MOD;
            }
        }
        
        return result;
    }
};

class Solution:
    def distinctSequences(self, n: int) -> int:
        if n == 1:
            return 6
        
        MOD = 10**9 + 7
        
        # 预处理互质关系
        def gcd(a, b):
            while b:
                a, b = b, a % b
            return a
        
        coprime = [[False] * 7 for _ in range(7)]
        for i in range(1, 7):
            for j in range(1, 7):
                coprime[i][j] = gcd(i, j) == 1
        
        # dp[i][j][k] 表示第i次掷骰子，前一次是j，当前是k的方案数
        dp = [[[0] * 7 for _ in range(7)] for _ in range(n + 1)]
        
        # 初始化前两次掷骰子
        for j in range(1, 7):
            for k in range(1, 7):
                if coprime[j][k] and j != k:
                    dp[2][j][k] = 1
        
        # 填充dp表
        for i in range(3, n + 1):
            for j in range(1, 7):
                for k in range(1, 7):
                    for next_val in range(1, 7):
                        if coprime[k][next_val] and k != next_val:
                            dp[i][k][next_val] = (dp[i][k][next_val] + dp[i-1][j][k]) % MOD
        
        result = 0
        for j in range(1, 7):
            for k in range(1, 7):
                result = (result + dp[n][j][k]) % MOD
        
        return result

public class Solution {
    public int DistinctSequences(int n) {
        if (n == 1) return 6;
        
        const int MOD = 1000000007;
        
        // 预处理互质关系
        bool[,] coprime = new bool[7, 7];
        for (int i = 1; i <= 6; i++) {
            for (int j = 1; j <= 6; j++) {
                coprime[i, j] = Gcd(i, j) == 1;
            }
        }
        
        // dp[i][j][k] 表示第i次掷骰子，前一次是j，当前是k的方案数
        long[,,] dp = new long[n + 1, 7, 7];
        
        // 初始化前两次掷骰子
        for (int j = 1; j <= 6; j++) {
            for (int k = 1; k <= 6; k++) {
                if (coprime[j, k] && j != k) {
                    dp[2, j, k] = 1;
                }
            }
        }
        
        // 填充dp表
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= 6; j++) {
                for (int k = 1; k <= 6; k++) {
                    for (int next = 1; next <= 6; next++) {
                        if (coprime[k, next] && k != next) {
                            dp[i, k, next] = (dp[i, k, next] + dp[i-1, j, k]) % MOD;
                        }
                    }
                }
            }
        }
        
        long result = 0;
        for (int j = 1; j <= 6; j++) {
            for (int k = 1; k <= 6; k++) {
                result = (result + dp[n, j, k]) % MOD;
            }
        }
        
        return (int)result;
    }
    
    private int Gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

var distinctSequences = function(n) {
    if (n === 1) return 6;
    
    const MOD = 1e9 + 7;
    
    function gcd(a, b) {
        return b === 0 ? a : gcd(b, a % b);
    }
    
    // Check if two dice values can be adjacent
    function canBeAdjacent(a, b) {
        return gcd(a, b) === 1;
    }
    
    // dp[i][j][k] = number of sequences of length i ending with j and k as last two values
    const dp = Array(n + 1).fill(null).map(() => 
        Array(7).fill(null).map(() => Array(7).fill(0))
    );
    
    // Initialize for length 2
    for (let j = 1; j <= 6; j++) {
        for (let k = 1; k <= 6; k++) {
            if (j !== k && canBeAdjacent(j, k)) {
                dp[2][j][k] = 1;
            }
        }
    }
    
    // Fill dp table
    for (let i = 3; i <= n; i++) {
        for (let j = 1; j <= 6; j++) {
            for (let k = 1; k <= 6; k++) {
                if (j !== k && canBeAdjacent(j, k)) {
                    for (let prev = 1; prev <= 6; prev++) {
                        if (prev !== j && prev !== k) {
                            dp[i][j][k] = (dp[i][j][k] + dp[i-1][prev][j]) % MOD;
                        }
                    }
                }
            }
        }
    }
    
    // Sum all possibilities for length n
    let result = 0;
    for (let j = 1; j <= 6; j++) {
        for (let k = 1; k <= 6; k++) {
            result = (result + dp[n][j][k]) % MOD;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)三重循环遍历状态，每层最多6个值，常数时间
空间复杂度O(n)dp数组大小为n×6×6

相关题目