题解 | #牛牛爱花#

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

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

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

方法一：动态规划思想求解

求解思路
对于本题目的求解，我们采用动态规划的思想进行问题的求解。首先我们对每一行种花的情况进行讨论，发现00000011、00001000、00001001这三种情况在动态规划求解时会发生错误，因此我们对这三种情况进行单独地讨论。然后我们定义dp[i][j]表示第i列的j情况的方案数，因此我们秩序遍历一遍dp数组，即可得到本问题的答案。

图片说明

解题代码

class Solution {
public:
    int solve(int n) {
        int mod = 1e9 + 7;
        vector<vector<int> > mydp(n + 1, vector<int>(8, 0)); // 保存每列每个状态的花数
        mydp[0][0] = 1;
        int mycur, mypre;
        for(int i = 1; i <= n; i++)
        {
            mycur = i; // 当前坐标
            mypre = i - 1;
            for(int mask = 0; mask < 8; mask++)
            {
                if(mask == 3 || mask == 6 || mask == 7) // 排除三种特殊情况
                    continue;
                for(int k = 0; k < 8; k++)
                {
                    if(k == 3 || k == 6 || k == 7) // 对三种情况进行特殊讨论
                        continue;
                    if(mask & k)
                        continue;
                    mydp[mycur][mask] = (mydp[mycur][mask] + mydp[mypre][k]) % mod; //前一列转移到当前列
                }
            }
        }
        int myres = 0;
        for(int i = 0; i < 8; i++)
            myres = (myres + mydp[n][i]) % mod; // 最后一列所有元素相加
        return (myres - 1) % mod; // 去掉全部取0，并返回结果即可
    }
};

复杂度分析
时间复杂度：外层循环次数为N，内层循环为常数，因此时间复杂度为 $O(N)$
空间复杂度：使用辅助数组dp[N]，因此空间复杂度为 $O(N)$

方法二：优化思想求解

求解思路
对于方法一中的dp数组，我们可以对上述提到的三种特殊情况进行直接处理，即将他们赋值为旁边的数值。然后我们即可找到前一列中的对应下表，并将其全部相加即可。基于上述的思路我们对方法一进行优化，并得到本题的答案。

图片说明

解题代码

class Solution {
public:
    int solve(int n) {
        int mod = 1e9 + 7;
        vector<vector<int> > mydp(2, vector<int>(5, 0)); // 保存每列每个状态的花数
        mydp[0][0] = 1, mydp[0][1] = 1, mydp[0][2] = 1, mydp[0][3] = 1, mydp[0][4] = 1; // 更新首列为1
        int cur = 0, pre = 1;
        for(int i = 1; i < n; i++)
        {
            int temp = cur; // 常规的交换语句
            cur = pre;
            pre = temp;
            mydp[cur][0] = ((mydp[pre][1] + mydp[pre][2]) % mod + mydp[pre][4]) % mod; // 对特殊情况进行处理
            mydp[cur][1] = (((mydp[pre][0] + mydp[pre][2]) % mod + mydp[pre][3]) % mod + mydp[pre][4]) % mod;
            mydp[cur][2] = ((mydp[pre][0] + mydp[pre][1]) % mod + mydp[pre][4]) % mod;
            mydp[cur][3] = (mydp[pre][1] + mydp[pre][4]) % mod;
            mydp[cur][4] = ((((mydp[pre][0] + mydp[pre][1]) % mod + mydp[pre][2]) % mod + mydp[pre][3]) %mod + mydp[pre][4]) % mod;
        }
        int myres = 0;
        for(int i = 0; i < 5; i++)
            myres = (myres + mydp[cur][i]) % mod; //最后一列所有元素相加
        return (myres - 1) % mod; // 去掉全部取0的情况，res减1，得到最后的结果
    }
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：dp[][]是常数数组，使用常数级内存地址空间，因此空间复杂度为 $O(1)$