[leetcode 2318][三维DP][二维DP]不同骰子序列的数目

题目链接

leetcode 2318 不同骰子序列的数目

解题思路

深度搜索遍历(超时)

建立一个数组记录第i位及以前的数字，遍历所有符合要求的数字 

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
const MOD = int64(1e9 + 7)

func gcd(a int, b int) int {
	n, m := max(a, b), min(a, b)
	if m == 0 {
		return n
	}
	return gcd(m, n%m)
}

func distinctSequences(n int) int {
	var dfs func(n int) int64
	var dp = make([]int, n)
	dfs = func(i int) int64 {
		if i == n {
			return 1
		}
		sum := int64(0)
		for m := 1; m <= 6; m++ {
			if (i < 2 || dp[i-2] != m) && (i < 1 || dp[i-1] != m) && (i < 1 || gcd(dp[i-1], m) == 1) {
				dp[i] = m
				sum = (sum + dfs(i+1)) % MOD
			}
		}
		return sum
	}
	return int(dfs(0))
}
整体时间复杂度为

三维DP

声明dp，dp[i][j][k]表示i-1个骰子以j和k结尾的子序列数量，例如dp[5][3][4]即为投出五个骰子以3为倒数第二个数4为倒数第一个数的子序列数量 

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
const MOD = int64(1e9 + 7)

func gcd(a int, b int) int {
	n, m := max(a, b), min(a, b)
	if m == 0 {
		return n
	}
	return gcd(m, n%m)
}

func distinctSequences(n int) int {
    //特判
	if n == 1 {
		return 6
	}
	var dp = make([][][]int64, n)
	for i := range dp {
		dp[i] = make([][]int64, 7)
		for j := range dp[i] {
			dp[i][j] = make([]int64, 7)
		}
	}
    //n > 1时开始初始化dp数组
	for j := 1; j <= 6; j++ {
		for i := 1; i <= 6; i++ {
			if i != j && gcd(i, j) == 1 {
				dp[1][i][j] = 1
			}
		}
	}
	for i := 2; i < n; i++ {
		for n1 := 1; n1 <= 6; n1++ {
			for n2 := 1; n2 <= 6; n2++ {
				for n3 := 1; n3 <= 6; n3++ {
    //枚举结尾三个数，当三个数互不相等且相邻数字两两互质则满足条件
					if n1 != n2 && n1 != n3 && n2 != n3 && gcd(n1, n2) == 1 && gcd(n2, n3) == 1 {
						dp[i][n2][n1] = (dp[i][n2][n1] + dp[i-1][n3][n2]) % MOD
					}
				}
			}
		}
	}

	sum := int64(0)

	for _, v1 := range dp[n-1] {
		for _, v2 := range v1 {
			sum = (sum + v2) % MOD
		}
	}
	return int(sum)
}

二维DP

声明dp，dp[i][j]表示投出i+1个骰子以j结尾的子序列数量，那么dp[i][j]则应该等于dp[i-1][k](k != j && gcd(j,k)==1)的和，但由于j和k满足条件那么dp[i-1][k]必定包括dp[i-2][j]的情况，状态转义方程则为 但上面的状态转移方程在n大于等于4时结果则小于正确答案（例如n等于4时输出162,正确答案184）。这是因为dp[i-1][k]中不含有dp[i-3][k]的情况，但dp[i-2][k]中有，所以导致减去的比实际情况多，但因为与j与k符合条件所以，所以只要加上一次dp[i-2][j]就能纠正错误。综上所述，正确状态转移方程为 

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
39
40
41
42
43
const MOD = int64(1e9 + 7)

func gcd(a int, b int) int {
	n, m := max(a, b), min(a, b)
	if m == 0 {
		return n
	}
	return gcd(m, n%m)
}

func distinctSequences(n int) int {
	var dp = make([][]int64, n)
	for i := range dp {
		dp[i] = make([]int64, 7)
	}
	for i := 1; i <= 6; i++ {
		dp[0][i] = 1
	}
	for i := 1; i < n; i++ {
		for j := 1; j <= 6; j++ {
			for k := 1; k <= 6; k++ {
				if j != k && gcd(j, k) == 1 {
					dp[i][j] += dp[i-1][k]
					if i >= 2 {
						dp[i][j] -= dp[i-2][j]
                        //防止dp[i-2][j]的余数比dp[i-1][k]大产生负数
						dp[i][j] += MOD
					}
				}
			}
            //只有在n >= 4时才会出现上述问题
			if i > 2 {
				dp[i][j] += dp[i-2][j]
			}
			dp[i][j] %= MOD
		}
	}
	sum := int64(0)
	for i := 1; i <= 6; i++ {
		sum = (dp[n-1][i] + sum) % MOD
	}
	return int(sum)
}