题解 | #牛牛爱花#

思路：

题目的主要信息：
种花土地大小为3*n，1≤n≤1e5，根据题目要求，种花时需要满足以下两种条件：

• 土地上至少要有一朵花

• 每朵花的上下左右不能有花

  方法一：动态规划

  根据题目信息，总共有n列3x1的土地，如果用1代表在这格上种花，0代表这格不种花，在3x1的土地上种花有以下几种情况：
  
  我们用0、1、2、3、4、5、6、7来代表这八种种花方案。
  题目要求每朵花的上下左右不能有花，所以对于每一列3x1的土地都排除3、6、7三种情况，这三种情况会发生上下冲突。因此每一列土地可能的种花情况有0、1、2、4、5五种情况。我们用动态规划进行求解，首先建立一个nx8的dp数组。n代表总共有n列，依次是第0列、第1列……第n-1列，每一列有8种种花方案（实际上是五种，排除了3、6、7）。
  dp[col][i]的含义是第col列为i方案时，这片土地总共有多少种花方案。在计算dp[col][i]的时候需要遍历考虑到前一列的情况，需要判断两列的花是否会冲突，用来“与”操作判断两列是否会冲突，如果冲突则跳过这种情况；如果不冲突，则累计dp[col-1][j]方案数到dp[col][i]上。
  根据dp[col][i]的含义，最后总的方案数是dp[n-1][i] (i=0,1,2,4,5)的总和。由于土地上必须有一朵花，动态规划的过程中我们没有剔除这种情况，因此在返回结果时要减去这种情况。

• 具体做法：*

  class Solution {
  public:
     /**
      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
      *
      * 
      * @param n int整型 列数
      * @return int整型
      */
     int solve(int n) {
         // write code here
         vector<vector<int>> dp(n,vector<int>(8,0));
         int mod=1e9+7;
         for(int i=0;i<8;i++)
         {
             if(i==3||i==6||i==7) continue;
             dp[0][i]=1;//对一列的情况进行初始化
         }
         for(int col=1;col<n;col++)//逐列查看情况
         {
             for(int i=0;i<8;i++)
             {
                 if(i==3||i==6||i==7) continue;//跳过这三种非法情况
                 for(int j=0;j<8;j++)
                 {
                     if(j==3||j==6||j==7) continue;
                     if(i&j) continue;//i与j两种情况不能同时存在，会有冲突
                     dp[col][i]=(dp[col][i]+dp[col-1][j])%mod;//计算第col列为i种花方式时有多少方案
                     //cout<<"dp["<<col<<"]"<<"["<<i<<"]"<<" "<<dp[col][i]<<endl;
                 }
             }
         }
         int result=0;
         for(int i=0;i<8;i++)
         {
             if(i==3||i==6||i==7) continue;
             result=(result+dp[n-1][i])%mod;//累积每种情况，计算总的方案数
         }
         result-=1;//剔除土地上没有花的情况
         return result;
  
     }
  };

复杂度分析：

• 时间复杂度： ,当n远大于8时，为 。
• 空间复杂度： ,动态规划数组dp为nx8大小。

方法二：动态规划优化

对方法一的动态规划进行优化可以减少时间和空间占用。首先我们在判断两列的花是否会冲突的时候只需要用到当前列和前一列，所以dp数组可以从nx8大小改为2x8的大小，循环利用数组存储当前列和前一列的内容。
其次，对于会发生冲突的情况可以提前计算好，例如0与0、1、2、4、5都不会冲突。每一种方案对应的不冲突情况如下图所示：

知道每一方案不冲突的方案后，就可以去掉两重循环，大大减少了时间复杂度。
最后计算总方案数只需要把dp[current][i] (i=0,1,2,4,5)相加，再剔除全0的情况。
注意：直接相加的过程每一步都需要对1e9+7取模。
具体做法：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 列数
     * @return int整型
     */
    int solve(int n) {
        // write code here
        vector<vector<int>> dp(2,vector<int>(8,0));
        int mod=1e9+7;
        for(int i=0;i<8;i++)
        {
            if(i==3||i==6||i==7) continue;
            dp[0][i]=1;//对一列的情况进行初始化
        }
        int current=0;
        int pre=1;
        int temp;
        for(int col=1;col<n;col++)//逐列查看情况
        {
            temp=pre;
            pre=current;
            current=temp;//循环利用dp数组节省空间
            //接下来利用已知的情况直接计算
            dp[current][0] = ((((dp[pre][0] + dp[pre][1]) % mod + dp[pre][2]) % mod+ dp[pre][4]) % mod+ dp[pre][5]) % mod;//0与0、1、2、4、5不冲突
            dp[current][1] = ((dp[pre][0] + dp[pre][2]) % mod+ dp[pre][4]) % mod;//1与0、2、4不冲突
            dp[current][2] = (((dp[pre][0] + dp[pre][1]) %mod + dp[pre][4]) % mod+ dp[pre][5]) % mod;//2与0、1、4、5不冲突
            dp[current][4] = ((dp[pre][0] + dp[pre][1]) % mod + dp[pre][2]) % mod;//4与0、1、2不冲突
            dp[current][5] = (dp[pre][0] + dp[pre][2]) % mod;//5与0、2不冲突

        }
        int result=0;
        for(int i=0;i<8;i++)
        {
            if(i==3||i==6||i==7) continue;
            result=(result+dp[current][i])%mod;//累积每种情况，计算总的方案数
        }
        result-=1;//剔除土地上没有花的情况
        return result;

    }
};

复杂度分析：

• 时间复杂度： ,一层遍历。
• 空间复杂度： ,只用到了2x8规格的dp数组，为常数空间。