MatRush@ZJUT

如图：

对于给定的2*n格方块，可以由摆放好的2*(n-1)的方块加上一块竖直的2*1方块或者由摆放好的2*(n-2)的方块加上两块横着的2*1方块组合而来。
容易得出状态转移方程为著名的斐波那契数列：

f[n] = f[n-1] + f[n-2]，

边界条件

f[1] = 1,f[2] = 2;

代码如下:

/*
ID:Shuaicpp
Prog:HDU2046-骨牌铺方格
Lang:C++
Algorithm:DP-f[i]=f[i-1]+f[i-2];
*/
#include <iostream>
using namespace std;
const int n = 51;
long long f[n] = {0};
int main()
{
   f[1] = 1;
   f[2] = 2;
   f[3] = 3;
   for (int i = 4;i < n;i++)
       f[i] = f[i-1] + f[i-2];
   int x;
   while (cin >> x)
       cout << f[x] << endl;
   return 0;
}