leetcode：6107. 不同骰子序列的数目【dp六个状态 + dfs记忆化】

分析

对于记忆化搜索，一定是固定参数的dfs的值是一样的，所以要想好设置什么参数和返回什么值
这里的话，参数可以设置n长度，last上一个 和last2上上个
值的话就设置为不同的序列数
特别的，当n是0的时候，没得选也算一种
注意，初始值可以设置为7，7（两个last）说明可以任选
这里我们的函数意思是# f:后面还有n个，前面两个分别是last和last2

dfs + cache

# f:后面还有n个，前面两个分别是last和last2

@cache
def f(n: int, last: int, last2: int) -> int:
    #print(n, last, last2)
    # 退出条件：后面没有了（没有了就是一种选法）
    if n == 0: return 1 
    res = 0
    for j in range(1, 7): # 从第一位开始选
        if j != last and j != last2 and gcd(j, last) == 1:
            res += f(n - 1, j, last)
    return res % (10 ** 9 + 7)

class Solution:
    def distinctSequences(self, n: int) -> int:
        return f(n, 7, 7)  # 7 与 [1,6] 内的数字都不同且互质
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

dp

每个值维护6个状态（以这六个状态作为结尾的个数），前三个先手写出来
从第四个开始，选定了dp[i][j]后先把所有能选的dp[i - 1][k]加起来，由于last2和j不能相同，所以要减去dp[i - 2][j]
注意到如果i-2选择j的话，实际上i - 1是有dp[2][j]中选法的，但是由于i - 1和i - 3不能相同，导致i - 1只有dp[2][j] - 1中选法 比较绕
举例：dp[i][0] = dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][5] - dp[i - 2][0] * (dp[2][0] - 1)

dp code

class Solution:
    def distinctSequences(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        if n == 1:
            return 6
        if n == 2:
            return 22
        if n == 3:
            return 66
        
        dp = [[0] * 6 for _ in range(n + 1)]
        dp[1] = [1] * 6
        dp[2] = [5, 3, 4, 3, 5, 2]
        dp[3] = [12, 11, 12, 11, 12, 8]
        
        #mapp = {1:}
    
                    
        for i in range(4, n + 1):
            dp[i][0] = dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][5] - dp[i - 2][0] * (dp[2][0] - 1)
            dp[i][1] = dp[i - 1][0] + dp[i - 1][2] + dp[i - 1][4] - dp[i - 2][1] * (dp[2][1] - 1)
            dp[i][2] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][3] + dp[i - 1][4] - dp[i - 2][2] * (dp[2][2] - 1)
            dp[i][3] = dp[i - 1][0] + dp[i - 1][2] + dp[i - 1][4] - dp[i - 2][3] * (dp[2][3] - 1)
            dp[i][4] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][5] - dp[i - 2][4] * (dp[2][4] - 1)
            dp[i][5] = dp[i - 1][0] + dp[i - 1][4] - dp[i - 2][5] * (dp[2][5] - 1)
            
        #print(dp)
            
        
        return sum(dp[-1]) % MOD
                
            
            
                
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

总结

dfs + cache很优雅，要想好dfs的含义，以及每个参数的意义，和返回值的结果，当我们固定了参数返回值就应该是固定的
dp + 多状态很有意思，通过以哪个结尾分成六种dp，然后dp间互相作用（前三个），关系很复杂。。