用两个不同的瓷砖填充一个 2*n 的房间

Question

我遇到了一个问题，我必须填充一个有 2 行 n 列的矩形。有两块瓷砖，一个是 1*2 瓷砖，第二个是 L 形瓷砖，较大的边尺寸为 2 个单位，较小的边尺寸为 1 个单位。

我通过动态规划解决了它，但不确定它是否正常工作。如果不是，这个问题的正确自下而上代码是什么。下面是我的解决方案的功能片段。

对于循环，一列可以用一种方式填充，将第一个瓦片垂直放置，两个相邻的列可以通过一个接一个水平放置第一种瓦片来以一种方式填充。相邻的两列可以用两个L型的2种倒置方式来填充，相邻的4个列可以用两个L型的瓦片相对，第一种瓦片以两种方式水平放置。

int tileways(int n) //n=no.of columns of the rectangle.
{
    int i;
    int a[n+4];
    a[0]=0;
    a[1]=0;
    a[2]=0;
    a[3]=1;
    for(i=4;i<n+4;i++)
    {
        a[i]=a[i-1]+a[i-2]+2*a[i-3]+2*a[i-4];
    }
    return a[n+3];
}

Answer 1

使用我第一条评论中的方法。

l[3]配置：

L[3] 配置：

#include <iostream>
using namespace std;

int tileways(int n) //n=no.of columns of the rectangle.
{
    int l[20];//straight border
    int L[20];//extra square
    l[0] = 1; 
    l[1] = 1;
    L[0] = 0;
    L[1] = 1;
    for (int i = 2; i <=n; i++) {

        l[i] = l[i-1] + l[i-2] + 2*L[i-2]; 
        //add | to the last straight, = to the 2nd last straight, 
        //two cases of L to extra

        L[i] = l[i-1] + L[i-1];
        //add L to the last straight, - to the extra 
    }
    return l[n];
}

int main() {
    for (int i = 1; i < 10; i++) 
        std::cout<<i<<" "<< tileways(i)<<std::endl;
    return 0;
}

ideone 结果

供参考：OEIS sequence number of possible tilings of a 2 X n board, using dominos and L-shaped trominos.

1, 2, 5, 11, 24, 53, 117, 258

用两个不同的瓷砖填充一个 2*n 的房间

Filling a 2*n room with two different tiles

c++

algorithm

dynamic-programming

data-structures