牛牛爱花

[编程题]牛牛爱花

热度指数：1223 时间限制：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]四种

备注:

算法知识视频讲解

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)