Problem D: 骨牌铺法(domino)
Time Limit: 4 Sec Memory Limit: 128 MBSubmit: 298 Solved: 122
[Submit] [Status] [Web Board] [Creator:]
Description
有 1×n 的一个长方形，用一个 1×1、1×2 和 1×3 的骨牌铺满方格。例如当 n=3 时为 1×3 的方格。
此时用 1×1、1×2 和 1×3 的骨牌铺满方格，共有四种铺法。如下图： 
Input
输入整数n。
Output
输出方法数。
Sample Input Copy
3
Sample Output Copy
4
HINT
【题解】
假设我们现在要铺第4格，我们可以在铺满第一格的时候加上一块1*3的骨牌，也可以在铺满前两格的时候铺上一块1*2的骨牌，也可以在铺满前3格的时候铺上一块1*1的骨牌。
而铺满一块，两块，3块的方法，很容易就能得到。
由此可以得到一个递推式，即a[i]=a[i-1] + a[i-2] +a[i-3];