牛牛爱花

[编程题]牛牛爱花

热度指数：1223 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛有一个3*n的土地。这个土地有3行，n列。牛牛想在土地上种至少一朵花。

为了花儿能够茁壮成长，每一朵花的上下左右四个方向不能有其他的花。问有多少种种花的方案。

为防止答案过大，答案对1e9+7取模。

示例1

输入

输出

说明

只有1列，用1代表花，0代表空地。这一列的种法可能是[1,0,0],[0,1,0],[0,0,1],[1,0,1]四种

备注:

算法知识视频讲解

Python 3

ZhongHaoWang

状态压缩dp

class Solution:
    def solve(self , n ):
        # write code here
        mod = 10 ** 9 + 7
        
        dp = [[0 for i in range(1 << 3)] for i in range(n)]
        
        valid = {0,1,2,4,5}
            
        # 0表示不种,1表示种
        for i in range(n):
            for state in range(1 << 3):
                # 判断当前是否是合法状态 
                if state in valid:
                    if i == 0:
                        dp[i][state] = 1
                        continue
                    for last_state in range(1 << 3):
                        if last_state in valid and last_state & state == 0:
                            # 枚举是否合法
                            dp[i][state] += dp[i - 1][last_state] % mod
        return sum(dp[-1]) % mod - 1

发表于 2021-08-29 14:00:41 回复(0)