动态规划问题(2022蓝桥杯积木画题目)-创新互联
超详细傻瓜级教学,包看包会。
创新互联主营靖州网站建设的网络公司,主营网站建设方案,重庆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元起,快前往官网查看详情吧
当前标题:动态规划问题(2022蓝桥杯积木画题目)-创新互联
标题来源:http://hbruida.cn/article/cohiej.html