HDU 2046 骨牌铺方格

解题报告：

题目大意：给你一个n ，表示有2*n规格的方格，现在又若干个1*2规格的骨牌，要用骨牌将2*n 规格的方格铺满，问有多少种铺法。

动态规划题，要求有n格时铺的方法种数，就可以通过有n-1跟n-2个方格的结果来递推出来，思想就是当要求有n个方格时铺的方法种数就可以理解为在n-1格的情况下，多了一个

格，那么着多出的一个就可以直接将一块骨牌竖直放好就可以填满了，然而还要加上有将两块骨牌横着放的情况，这时就需要有两个空的方格，于是我们可以由n-2个方格的情况递推过来，也就是加上一个n-2的情况，可以定义一个数组DP【55】，首先将数组DP初始化为DP[1]=1;DP[2]=2;DP[3]=3;得出的递推公式就是DP[n]=DP[n-1]+DP[n-2]。

View Code

 1 #include<stdio.h>
 2 __int64 DP[55],n;
 3 void dabiao(void) {
 4     DP[1]=1,DP[2]=2,DP[3]=3;
 5     for(int i=4;i<=51;++i)
 6     DP[i]=DP[i-1]+DP[i-2];
 7 }
 8 int main() {
 9     dabiao();
10     while(scanf("%I64d",&n)!=EOF)
11     printf("%I64d\n",DP[n]);
12 }