题解 | #牛牛爱花#

思路

题目分析

我们有一块大小为3*n的土地，n即为我们的输入
这块土地可以种花，要求花和花之间上下左右不可相邻，且至少要种一朵，只要花种的位置不同就视作不同的种植方案
输出可以种花的方案数

我们发现，种植的行数是固定的 = 3
因此每一列的种植情况是死的，我们暂时不考虑至少要种一朵这个条件，因此比如某一列就可以种植的方案只能是[0,0,0],[1,0,0],[0,1,0],[0,0,1],[1,0,1]5种
而相邻列具有相关性，我们根据这种相关性递推下一列的方案数，比如
- 当前列如果为[0,0,0]，则下一列可以选的方案数就是5种
- 如果当前列为[1,0,0]，则下一列可选的方案只能是[0,0,0],[0,1,0],[0,0,1]共3种
- 其他情况依次类推
因此我们只要迭代每一个下一列的方案数，并进行统计，最终就会获得总共的方案数
这时我们再考虑至少种一朵的条件，我们只要在以上的总数基础上-1，即减去土地上每一列全为0这一种种植
方案，即最终结果。

方法一：动态规划

我们开辟一块 5*n 大小的二维数组c
初始化c[0,1,2,3,4][0] = 1，即第一列全部初始化为1
我们采用二维数组的方式进行统计，对于j >= 1的情况，将二维数组c[i][j]定义为对于第j+1列，如果前一列种植方案为i，则当前第j+1列的种植方案数量累计为c[i][j]。

图片说明

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 列数
# @return int整型
#
class Solution:
    def solve(self , n ):
        # write code here
        mod = 1e9+7
        c = [[1 for i in range(n)] for i in range(5)]        # 开辟二维数组
        for i in range(1,n):                                 # 对于前一列的五种情况进行分类统计
            c[0][i] = (c[0][i-1] + c[1][i-1] + c[2][i-1] + c[3][i-1] + c[4][i-1]) % mod 
            c[1][i] = (c[0][i-1] + c[2][i-1] + c[3][i-1]) % mod 
            c[2][i] = (c[0][i-1] + c[1][i-1] + c[3][i-1] + c[4][i-1]) % mod 
            c[3][i] = (c[0][i-1] + c[1][i-1] + c[2][i-1]) % mod 
            c[4][i] = (c[0][i-1] + c[2][i-1]) % mod 
        b = 0
        b += (sum(i[-1] for i in c) - 1) % mod               # 直接获取最后一列的统计结果，并使用-1修正
        return int(b)

复杂度分析

时间复杂度： $O(N)$ ，单重循环
空间复杂度： $O(N)$ ，申请了 $5*N$ 大小的空间

方法二：动态规划优化空间

第一种方法我们消耗了太多的额外空间，使用很大的二维列表规模
我们发现动态规划递推过程中，只有前后两列有关系，因此我们可以只存储前后两列的信息不断迭代优化空间

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 列数
# @return int整型
#
class Solution:
    def solve(self , n ):
        # write code here
        mod = 1e9+7
        curcase = [1,1,1,1,1]            # 当前列的情况
        precase = curcase[:]             # 前一列的情况
        for i in range(1,n):
            curcase[0] = (precase[0] + precase[1] + precase[2] + precase[3] + precase[4]) % mod
            curcase[1] = (precase[0] + precase[2] + precase[3]) % mod
            curcase[2] = (precase[0] + precase[1] + precase[3] + precase[4]) % mod 
            curcase[3] = (precase[0] + precase[1] + precase[2]) % mod 
            curcase[4] = (precase[0] + precase[2]) % mod 
            precase = curcase[:]        # 每一轮累计后，当前列变成了下一轮的前一列
        a = sum(curcase, -1) % mod
        return int(a)

复杂度分析

时间复杂度： $O(N)$ ，单重循环
空间复杂度： $O(1)$ ，申请了常数大小的空间，两个列表存储