题解 | #牛牛爱花#

思路：

题目的主要信息：

• 一个的土地，至少种一株花
• 当某个位置种了花，其上下左右不能再有花，问种花的方案数
• 数比较大，需要返回

方法一：动态规划
具体做法：
首先解决上下花不能邻近的问题，如下图：

图中每列表示三行中的任意一列，对于任意一列，我们以0表示不种花，1表示种花，我们可以发现二进制数为3、6、7的种法不符合要求，因此我们可以用0-7表示列的种法，只要排除掉这三个数即可。
再来解决左右花不能邻近的问题，同样是上图，如果我们将其当成相邻的列，则会发现相邻列之间做位与运算如果结果是0，则符合要求。
这样我们可以考虑动态规划，表示第列在中情况时的方案数，我们只需要遍历1到n，将的dp数组补齐，在补齐的时候需要注意比较邻近列的位与才可以相加。最后将最后一列的8种搭配方案相加即可。
但是这并不是答案，因为题目要求必须有一枝花，而仔细观察我们的思路，我们将全0的情况也包含进去了，因此需要减去1。

class Solution {
public:
    int solve(int n) {
        int mod = 1e9 + 7;
        vector<vector<int> > dp(n + 1, vector<int>(8, 0)); //保存每列每个状态的花数
        dp[0][0] = 1;
        int cur, pre;
        for(int i = 1; i <= n; i++){
            cur = i;
            pre = 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;
                    dp[cur][mask] = (dp[cur][mask] + dp[pre][k]) % mod; //前一列转移到当前列
                }
            }
        }
        int res = 0;
        for(int i = 0; i < 8; i++)
            res = (res + dp[n][i]) % mod; //最后一列所有元素相加
        return (res - 1) % mod; //去掉全部取0
    }
};

复杂度分析：

• 时间复杂度：，内循环两轮为8，外循环为，当很大时，可等于
• 空间复杂度：，辅助数组dp，当很大时，可等于

方法二：动态规划空间优化
具体做法：
首先对于dp数组第一维的8个元素，我们其实根本就可以省略掉3、6、7的份额，每次相加的时候不用比较是否是3、6、7，也不用保存，也不用比较与旁边的差别，因为每当一个数出来的时候我们就直到它旁边是哪些可以了，如下图：

每种情况它旁边对应的都是已经，我们只需要找到前一列中的对应下标，将其全部相加即可。
再来解决dp数组二维的n和元素，其实在我们遍历的过程中，我们只用到了当前列和上一列，因此我们完全可以用两个下标来交换使用，当作当前列和上一列的不断滚动。
优化后的代码如下：

class Solution {
public:
    int solve(int n) {
        int mod = 1e9 + 7;
        vector<vector<int> > dp(2, vector<int>(5, 0)); //保存每列每个状态的花数
        dp[0][0] = 1, dp[0][1] = 1, dp[0][2] = 1, dp[0][3] = 1, dp[0][4] = 1; //更新首列为1
        int cur = 0, pre = 1;
        for(int i = 1; i < n; i++){
            int temp = cur;
            cur = pre;
            pre = temp;
            dp[cur][0] = ((dp[pre][1] + dp[pre][2]) % mod + dp[pre][4]) % mod;
            dp[cur][1] = (((dp[pre][0] + dp[pre][2]) % mod + dp[pre][3]) % mod + dp[pre][4]) % mod;
            dp[cur][2] = ((dp[pre][0] + dp[pre][1]) % mod + dp[pre][4]) % mod;
            dp[cur][3] = (dp[pre][1] + dp[pre][4]) % mod;
            dp[cur][4] = ((((dp[pre][0] + dp[pre][1]) % mod + dp[pre][2]) % mod + dp[pre][3]) %mod + dp[pre][4]) % mod;

        }
        int res = 0;
        for(int i = 0; i < 5; i++)
            res = (res + dp[cur][i]) % mod; //最后一列所有元素相加
        return (res - 1) % mod; //去掉全部取0
    }
};

复杂度分析：

• 时间复杂度：，只有一个循环
• 空间复杂度：，的辅助数组属于常数量级空间