【题解】Leetcode双周赛81 不同骰子序列的数目 困难

题目来源： Leetcode周赛81
标签：动态规划

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

• 序列中任意 相邻 数字的 最大公约数 为 1 。
• 序列中 相等 的值之间，至少有 2 个其他值的数字。正式地，如果第 i 次掷骰子的值 等于 第 j 次的值，那么 $abs(i-j)>2$ 。

请你返回不同序列的 总数目 。由于答案可能很大，请你将答案对 $10^9+7$ 取余 后返回。

如果两个序列中至少有一个元素不同，那么它们被视为不同的序列。

输入：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 。
1
2
3
4
5
6
7

由于第i个数字和第i-1和i-2个数字有限制要求，因此定义$dp[i][j][k]$：表示长度为 i ，最后两个数字分别为 j 和 k 且符合题目要求的序列数量。

对于最后两个数字分别为 j 和 k ，我们枚举倒数第三个数字 u 时，要求 u 和 j 的最大公约数是1并且 u != j、u != k，而如果我们将 u 和 j 作为序列的最后两个数字，并且要求u 和 j 的最大公约数是1 and u != j 限制条件我们可以联系到$dp[i-1][u][j]$。那么可以进行状态转移
$$dp[i][j][k]+=dp[i-1][u][j]$$

class Solution {
    private int gcd(int a,int b){
        return b != 0 ? gcd(b,a % b) : a;
    }
    public int distinctSequences(int n) {
        final int mod = 1000000007;
        // 特判，当n==1时直接返回答案
        if (n == 1) return 6;
        // dp[i][j][k]：表示长度为i的序列，最后两个数字分别为j和k的数量
        int [][][] dp = new int[n+1][6][6];
        // 初始化序列长度为2的情况
        for (int i= 0 ;i < 6;i++)
            for (int j = 0;j < 6;j++)
                if (gcd(i+1,j+1) == 1 && i != j) dp[2][i][j] = 1;
        //状态转移
        for (int i = 3;i <= n;i++){
            for (int j= 0 ;j < 6;j++){ // 倒数第二个数字
                for (int k = 0;k < 6;k++){ // 倒数第一个数字
                    if (gcd(j+1,k+1) == 1 && j != k){ //后两个数字不相等并且最大公约数为1才继续枚举倒数第三个数字 
                        for (int u = 0;u < 6;u++){ // 倒数第三个数字
                            if (gcd(u+1,j+1) == 1 && u != j && u != k){ // 根据题意进行判断
                                dp[i][j][k] = (dp[i][j][k] + dp[i-1][u][j]) % mod; //符合情况则累加答案
                            }
                        }
                    }
                }
            }
        }
        int ans = 0;
        // 目标：dp[n][j][k] j: 0~6 k:0~6
        for (int j = 0;j < 6;j++){
            for (int k =0;k < 6;k++){
                ans = (ans + dp[n][j][k]) % mod;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38