牛牛爱花_牛客博客

最优解法

用二进制[0~7]代表每一列的种花情况。用 $dp[i][mask]$ 代表有 $i$ 列且最后一列的种花情况为 $mask$ ，通过枚举有 $i-1$ 列的最后一列花的情况来转移。可以用滚动数组优化空间复杂度。
因为每一列种花情况只有5个状态是有效的，所以总的时间复杂度为 $O(5^2n)$ ，滚动数组优化后只用了一个2*8的辅助数组，空间复杂度可以视为 $O(1)$ 。

int solve(int n){
    int mod = 1e9 + 7;
    int dp[2][8]; memset(dp, 0, sizeof dp);
    int cur = 0, pre = 1;
    dp[0][0] = 1;
    for(int i = 0; i < n; ++i){
        swap(cur, pre);
        for(int j = 0; j < 8; ++j) dp[cur][j] = 0;
        for(int mask = 0; mask < 8; ++mask){//枚举当前列种花的情况
            if(mask == 3 || mask == 6 || mask == 7) continue;
            for(int t = 0; t < 8; ++t){//枚举上一列种花的情况
                if(t == 3 || t == 6 || t == 7) continue;
                if(mask&t) continue;//如果当前列的花和上一列的花有相邻的情况，则不转移
                dp[cur][mask] = (dp[cur][mask] + dp[pre][t])%mod;
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < 8; ++i) ans = (ans + dp[cur][i])%mod;
    return (ans + mod-1)%mod;
}