Description
有1×n(n<=50)的一个长方形,用一个1×1、1×2和1×3的骨牌铺满方格,请问有多少种铺法?
例如当n=3时为1×3的方格。此时用1×1、1×2和1×3的骨牌铺满方格,共有四种铺法。如下图:
HINT
n为4的时候,方法数F4的分析如下:
第一块放1*1,有一种方法;剩余3块方法数是F3=4种。根据乘法原理,该种情况的方法数是1*4=4。
第一块放1*2,有一种方法;剩余2块方法数是F2=2种。根据乘法原理,该种情况的方法数是1*2=2.
第一块放1*3,有一种方法;剩余1块方法数是F1=1种。该种情况方法数是1*1=1.
根据分类原理,F4=4+2+1=7种。