我们先来看下题目给的案例:
首先我们直接来看三阶的,第一个和第二个我们可以发现I型积木拼放的方式是有2种的,或者看一和四都行,然后L型积木的拼接方式是1种看三和五(你把他们两个反转过来就是一种),那我们不妨想的简单一点所以递推公式就是:dp[i]=dp[i-1]*2+dp[i-3];
证明的方法就是我们刚才的思想过程,我们讲二维的矩阵看成了一维的,所以I型积木就是等于1个方格,所以我们记为i-1,L型积木就是等于1.5个方格,但是L型积木不能单独出现,必须成双的出现,所以我们记为i-3,又由于I型积木出现在一个位置有两种方式,所以我们乘以二,L型积木出现只有一直方式我们乘以1,就结束了。
但是我们还要进行初始化前三个:
#include<stdio.h> #include<string.h> #define mod 1000000007 int dp[10000005]; int main() { int n; scanf("%d",&n); memset(dp,0,sizeof(dp)); dp[1]=1,dp[2]=2,dp[3]=5; for(int i=4;i<=n;i++) { dp[i]=(dp[i-1]*2%mod+dp[i-3]%mod)%mod; } printf("%d\n",dp[n]); return 0; }
0.0分
42 人评分
2005年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:642 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:683 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:627 |
简单编码 (C++代码)浏览:678 |
十->二进制转换 (C语言代码)浏览:1291 |
C语言程序设计教程(第三版)课后习题6.2 (C语言代码)浏览:1420 |
C语言训练-求函数值 (C语言代码)浏览:580 |
DNA (C语言描述,蓝桥杯)浏览:1555 |
a+b浏览:433 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:684 |