首页 > 试题广场 >

牛牛爱花

[编程题]牛牛爱花

热度指数：1192 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

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

示例1

输入

输出

说明

只有1列，用1代表花，0代表空地。这一列的种法可能是[1,0,0],[0,1,0],[0,0,1],[1,0,1]四种

备注:

算法知识视频讲解

杭电5餐厨师长

解释一下题目：

题目其实类似于leetcode的房屋染色解法。当前列的选择，依赖与前一列的状态。

因为要求是3行，不考虑题目要求的话，第一列有几种种花方案呢？显然有2^3种组合。也就是000,001...111。一共这8种，用10进制数字表示的话，可以用0-7这8个数字来解释。但题目要求不能相邻。那么久排除掉了3,6,7这三种方案。也就是011,110,111这三种种植方案是明显不可以的。那么还剩5种方案。但题目同时要求，整个田地至少种一朵花。所以当n=1的时候，第一列不能取000这种状态。智能取001，010，100，101这四种状态。但当n=2的时候，前一列是可以取000这种状态的，只要n=2这一列不取000这种状态就好了。也就是说每一列全部都为000的这种情况是需要去掉的，其他情况都可以存在。因此，我们可以判断出每一列其实都有5种状态。最后把得到的总状态数-1即可。

n = 1 时，不需要考虑前一列的状态，因此这五种状态都为1。

n= i 且!=1时，需要考虑前一列的状态，需要判断是否相邻。判断是否相邻可以用&运算。比如001和101这两种就是相邻的，运算1&5得到的结果是1。每次计算当前列的方案数的时候，把前一列不相邻的所有状态数加起来即可。

举个例子。n=2时，有5种可能状态，分别是000，001，010，100，101。我分别把它极为dp[2][0],dp[2][1],dp[2][2],dp[2][4],dp[2][5]。剩下的三种状态dp[2][3],dp[2][6],dp[2][7]可以直接跳过。因为这三种状态是不符合要求的。那么dp[2][0] = 5。因为前面一列无论是哪种状态都不会与当前列冲突。dp[2][1] = 3 因为dp[2][1]与dp[1][1]冲突，与dp[1][5]冲突。同理可得dp[2][2] = 4,dp[2][4] = 3,dp[2][5]=2。所以当n=2时，它的所有方案数为sum(dp[2])。也就是17。但有一种方案是不可以的。也就是第一列状态是0，第二列状态也是0的情况。所以方案数是sum(dp[2])-1 。

注意：为了好描述问题。这里我用dp[2]来表示第二列。但在实际编程的时候，我用dp[1]表示第二列，dp[0]表示第一列。其实是一样的。

可能有人会问既然只有5种状态，为什么不用0,1,2,3,4,来标记着5种状态呢？其实主要是为了能够实现判断是否相邻的操作，如果用二进制来表示，那么就可以用与运算来判断这两列所插的花是否相邻了。如果想用这5种状态来做的话，参考我第一次的做法。

连接如下：

https://www.nowcoder.com/profile/1001612/codeBookDetail?submissionId=68841360

参考了 ”积极的防守者“的题解之后。

我写出了如下的代码：

#
(750)# 牛牛爱花
# @param n int整型 列数
(2215)# @return int整型
#
class Solution:
    def solve(self , n ):
        (2216)# write code here
        if n < 1:
            return n
        MOD = int(1e9+7)
        dp = [[0]*8 for _ in range(2)]
        dp[0] = [1,1,1,0,1,1,0,0]
        cur,pre = 0,1
        for i in range(n-1):
            cur,pre = pre,cur
            dp[cur] = [0]*8
            for j in range(8):
                if j==3&nbs***bsp;j == 6&nbs***bsp;j == 7:
                    continue
                # 枚举上一列的所有状态
                for k in range(8):
                    (2217)# k&j判断这两列的插花是否相邻
                    if k == 3&nbs***bsp;k == 6&nbs***bsp;k == 7&nbs***bsp;k&j :
                        continue
                    dp[cur][j] = (dp[cur][j]+dp[pre][k])%MOD
        return sum(dp[cur])%MOD-1

发表于 2020-03-11 22:46:16 回复(0)

C/C++

nbgao

class Solution {
public:
    /**
     * 牛牛爱花
     * @param n int整型 列数
     * @return int整型
     */
    // 000 001 010 100 101
    int solve(int n) {
        int M = 1e9+7;
        long dp[5]={1, 1, 1, 1, 1}, a[5];
        for(int i=2;i<=n;i++){
            a[0] = (dp[0]+dp[1]+dp[2]+dp[3]+dp[4])%M; // 000: 
            a[1] = (dp[0]+dp[2]+dp[3])%M;  //001
            a[2] = (dp[0]+dp[1]+dp[3]+dp[4])%M; // 010
            a[3] = (dp[0]+dp[1]+dp[2])%M;  // 100
            a[4] = (dp[0]+dp[2])%M;    // 101
            for(int j=0;j<5;j++)
                dp[j] = a[j];
        }
        return (dp[0]+dp[1]+dp[2]+dp[3]+dp[4]-1)%M;
    }
};

发表于 2020-08-15 01:20:36 回复(0)

yeshichen

基础DP

public int solve(int n) {
        long[][] dp = new long[n][1<<3];
        int mod = (int) (1e9 + 7);
        int[] vaild = new int[]{0, 1, 2, 4, 5};
        for (int v : vaild)
            dp[0][v] = 1;
        for (int i = 1; i < n; i++)
            for (int v : vaild)
                for (int k : vaild)
                    if ((v & k) == 0)
                        dp[i][v] = (dp[i][v] + dp[i - 1][k]) % mod;
        long sum = 0;
        for (int i = 0; i < 8; i++)
            sum = (sum + dp[n - 1][i]) % mod;
        return (int) (sum - 1);
    }

编辑于 2020-08-14 12:56:14 回复(0)

铁离子

/**每一列有五种状态，000，100，010，001，101，每一种状态前面的状态都是固定的，比如说100只能由000、010、001
*三种状态获得，这实际上就是一个状态机，因此递推可得答案。注意要减去所有列都为0的状态
*/
int solve(int n) {
        int mod = 1e9+7;
        vector<vector<long long> > dp(5,vector<long long>(n+1,1));
        for(int i=2;i<=n;i++){
            dp[0][i] = (dp[0][i-1]+dp[1][i-1]+dp[2][i-1]+dp[3][i-1]+dp[4][i-1])%mod;
            dp[1][i] = (dp[0][i-1]+dp[2][i-1]+dp[3][i-1])%mod;
            dp[2][i] = (dp[0][i-1]+dp[1][i-1]+dp[3][i-1]+dp[4][i-1])%mod;
            dp[3][i] = (dp[0][i-1]+dp[1][i-1]+dp[2][i-1])%mod;
            dp[4][i] = (dp[0][i-1]+dp[2][i-1])%mod;
        }
        return (dp[0][n]+dp[1][n]+dp[2][n]+dp[3][n]+dp[4][n]-1)%mod;
}

发表于 2020-04-12 12:35:48 回复(0)

Python 3

ZhongHaoWang

状态压缩dp

class Solution:
    def solve(self , n ):
        # write code here
        mod = 10 ** 9 + 7
        
        dp = [[0 for i in range(1 << 3)] for i in range(n)]
        
        valid = {0,1,2,4,5}
            
        # 0表示不种,1表示种
        for i in range(n):
            for state in range(1 << 3):
                # 判断当前是否是合法状态 
                if state in valid:
                    if i == 0:
                        dp[i][state] = 1
                        continue
                    for last_state in range(1 << 3):
                        if last_state in valid and last_state & state == 0:
                            # 枚举是否合法
                            dp[i][state] += dp[i - 1][last_state] % mod
        return sum(dp[-1]) % mod - 1

发表于 2021-08-29 14:00:41 回复(0)

梦醒时分201901032034795

class Solution {
public:
    int solve(int n) {
        int MOD = 1e9+7;
        vector<vector<long> > dp(5, vector<long>(n,0));
        for(int i = 0; i < 5; i++){
            dp[i][0] = 1;
        }
        
        for(int i = 1; i < n; i++){
           dp[0][i] = (dp[0][i - 1] + dp[1][i - 1] + dp[2][i - 1] + dp[3][i - 1] + dp[4][i - 1]) % MOD; //000
           dp[1][i] = (dp[0][i - 1] + dp[2][i - 1] + dp[3][i - 1]) % MOD;                               //001
           dp[2][i] = (dp[0][i - 1] + dp[1][i - 1] + dp[3][i - 1] + dp[4][i - 1]) % MOD;                //010
           dp[3][i] = (dp[0][i - 1] + dp[1][i - 1] + dp[2][i - 1]) % MOD;                               //100
           dp[4][i] = (dp[0][i - 1] + dp[2][i - 1]) % MOD;                                              //101
        }
        
        return (dp[0][n - 1] + dp[1][n - 1] + dp[2][n - 1] + dp[3][n - 1] + dp[4][n - 1] - 1) % MOD;
    }
};

发表于 2021-03-26 15:30:38 回复(0)

学问笃实生光辉

class Solution {
public:
        int res=0;
        long long m=1e9+7;
        vector<vector<long long>>dp(n,vector<long long>(5,0));
        dp[0][0]=dp[0][1]=dp[0][2]=dp[0][3]=dp[0][4]=1;
        for(int i=1;i<n;i++)
        {
            dp[i][0]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3]+dp[i-1][4])%m;
            dp[i][1]=(dp[i-1][0]+dp[i-1][2]+dp[i-1][3])%m;
            dp[i][2]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][1]+dp[i-1][4])%m;
            dp[i][3]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%m;
            dp[i][4]=(dp[i-1][0]+dp[i-1][2])%m;
        }
        res=(dp[n-1][0]+dp[n-1][1]+dp[n-1][2]+dp[n-1][3]+dp[n-1][4])%m;
        return res-1;
        
    }
};

发表于 2020-05-10 11:37:58 回复(0)

牛客722047690号

由于 6，7状态不合法，存储和判断可以直接忽略

发表于 2020-05-04 09:45:30 回复(0)

Java

offerPlusPlus_

public int solve (int n) {
        // write code here
        int[][] dp=new int[n][8];
        for (int i = 0; i < 7; i++) {
            if(i!=3&&i!=6&&i!=7){
                dp[0][i]=1;
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 7; j++) {
                if(j==3||j==6||j==7){
                    continue;
                }
                for (int k = 0; k < 7; k++) {
                    int x=j&k;
                    if(k==3||k==6||k==7||x!=0){
                        continue;
                    }
                    dp[i][j]=(dp[i][j]+dp[i-1][k])%((int)Math.pow(10,9)+7);
                }
            }
        }
        int res=-1;
        for (int i = 0; i < 7; i++) {
            if(i!=3&&i!=6&&i!=7){
                res=(res+dp[n-1][i])%((int)Math.pow(10,9)+7);
            }
        }
        return res;
    }

发表于 2020-03-25 15:44:55 回复(0)