斑的家

題意：給2種形狀一種1x1 大小的方格及3 個方格大小組成的L形。

給2x N 的長方形找出用方格及L形可以排出幾種可能？

解法： dynamic programming

稍微觀察一下，

2 x 1 有 1 種

2 x 2 有 5 種

2 x 3 有 11種

可以把大問題化成小問題

給2 x 4 的話，

先擺一個 2x1 的

*

*

剩下就是 2 x 3 。

如果擺一個 2 x 2

o *

o o

上面有四種可能

剩下就是 2 x 2 。

如果擺一個 2 x 3 的

o o o

o o o

上面有二種可能

剩下就是 2 x 1 。

所以得dp 公式 f(i) = f(i-1)+4*f(i-2) + 2*(f-3)。