13518219792
超详细傻瓜级教学，包看包会。
创新互联主营靖州网站建设的网络公司,主营网站建设方案,重庆APP软件开发,靖州h5微信小程序定制开发搭建,靖州网站营销推广欢迎靖州等地区企业咨询
关键思想：将2*1的画布看成初始画布，后面不断加1列空白列构成其他画布。所以最后一个画布的积木构成可以由之前的画布积木构成来推导。
下面为初始画布（仅有放一个i型积木的可能）
我们将画布上最后两格都空的情况称为情况0
只空上格称为情况1
只空下格称为情况2
不空称为情况3（即满足题目条件的情况）
所以定义一个二维数组dp[n+1][4]（动态规划算法简称DP，这个数组名就这样来的）
用来存储n长度画布的4种情况的可能的构成次数（即情况0123 为索引，所存的数为可能出现的构成的次数）
int[][] dp=new int[n+1][4];
dp[1][0]=1;
dp[1][3]=1;//情况初始化，初始画布下仅在情况3和情况0
一格画布只能出现情况3或0，12无法出现，所以将n=1时进行赋值。
再多一格时有这几种情况
即012的情况各有一种可能，3有两种可能
再往后添加一格空白，则012各有两种可能，3有五种可能
我们可以发现规律：
0情况就是上一个画布下3情况的可能（毕竟多加一列画布，前面是满的，后面多一列空白就满足了0情况）
1情况是上一个画布下0情况家+2情况的和 （即上一个画布的0情况加一个L型可满足，或上一个画布的2情况加一个横I型亦可满足）
情况2与情况1基本一样不再赘述
情况3（=上一个画布的情况0+情况1+情况2+情况3（如下图））
注意情况0的I型只能横放，否则与情况3重复。
则有如下代码
for(int i=2;i<=n;i++){
//情况0的计算
dp[i][0]=dp[i-1][3];
//情况1和2的计算
dp[i][1]=(dp[i-1][0]+dp[i-1][2])%mod;
dp[i][2]=(dp[i-1][0]+dp[i-1][1])%mod;
//情况3的计算
dp[i][3]=(((dp[i-1][0]+dp[i-1][1])%mod+dp[i-1][2])%mod+dp[i-1][3])%mod;
}
System.out.print(dp[n][3]);情况3的计算之所以要取模多次是为了保证不爆容器，毕竟一个数不论取多少次模都等于取一次模，所以无需在意多次取模对数据造成的影响。
最后输出dp[n][3]即为答案。完整代码如下
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int mod=1000000007;
int n=scan.nextInt();
int[][] dp=new int[n+1][4];
dp[1][0]=1;
dp[1][3]=1;//情况初始化，初始画布下仅在情况3
for(int i=2;i<=n;i++){
//情况0的计算
dp[i][0]=dp[i-1][3];
//情况1和2的计算
dp[i][1]=(dp[i-1][0]+dp[i-1][2])%mod;
dp[i][2]=(dp[i-1][0]+dp[i-1][1])%mod;
//情况3的计算
dp[i][3]=(((dp[i-1][0]+dp[i-1][1])%mod+dp[i-1][2])%mod+dp[i-1][3])%mod;
}
System.out.print(dp[n][3]);
scan.close();
}
}完！
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
