说说我的思路：

递推式：
f(n, state)
   =  3 * f(n-2, 0) + 2 * f(n-2, 1)  // when state is 0
or = f(n-2, 0) + f(n-2, 1)    // when state is 1

f(n, state) 表示有n列 而且格子状态是state时layout的种数
'state' is:
0: 表示这n列没有放置任何东西
1: 表示左上或者左下角两格已经放了东西，如图, x表示已经放了东西：
|-------
| x |  |
|-------
| x |  |
|------|
|      |
|------|

or:

|-------
|      |
|------|
| x |  |
|-------
| x |  |
|------|

对于f(n, state)， 当state为0时，可以有如下几种组合：
1:
|-------
|      |
|------|
|      |
|-------
|      |
|------|

2:
|-------
|   |  |
|   |  |
|   |  |
|-------
|      |
|------|

3:
|-------
|      |
|------|
|   |  |
|   |  |
|   |  |
|------|
对于这几种，问题转化为求f(n-2, 0)

还可以有如下组合:
|-----------|
|   |       |
|   |-------|
|   |       |
|-----------|
|      |
|------|
或者：
|------|
|      |
|-----------|
|   |       |
|   |-------|
|   |       |
|-----------|
对于这两种，问题转化为求f(n-2, 1)

当state为1(有两种，下面举在左上两格被占有为例)时, 可以有如下几种组合:
    ----
    |  |
    |  |
    |  |
|------|
|      |
|------|
对于这种，问题转化为求f(n-2, 0)
    --------
    |      |
    |------|
    |  
|----------|
|      |
|------|
对于这种，问题转化为求f(n-2, 1)

• 太漂亮了 (0) sjdeak 2015-12-27 16:28:13