Tri_Tiling

用2 * 1的小矩形 填充大小为3 * n的大矩形，问填充方案有多少种?（POJ 2663）

• 有两种求解方法：
  • 第一种用动态规划。
  • 用数学递推公式。

动态规划法

思路 ：

首先当n为奇数时，总有剩余1 * 1的小地方无法填补。

所以n必须为偶数，所以我们来分析下n为偶数时的情况。

当n = 2时，如图，以下三种填充方式。

当n = 4时，我们首先将n = 4分割为两个n = 2的填充方案组合成n = 4的填充方案有9种；但还有n = 4特有的不可分割的填充方案，如下图。将两个分割方案相加得n = 4的填充方案有11种。

当n = 6时， 我们首先将n = 6分割为三个n = 2的填充方案组合成n = 6的填充方案27种；还可以 将n = 6分割为一个n = 2与一个n = 4两个填充方案组合成的n = 6的填充方案12种；还有n = 6特有的不可分割的填充方案，如下图。将所有方案相加得n = 6的填充方案有41种。

当n = 8时， 我们首先将n = 8分割为四个n = 2的填充方案组合成n = 8的填充方案81种；还可以 将n = 8分割为两个n = 2与一个n = 4两个填充方案组合成的n = 8的填充方案54种；还可以将n = 8 分割为两个n = 4的填充方案组合成 n = 8的填充方案有4种；还可以将n = 8 分割为一个n = 6与一个n = 2的填充方案组合成n = 8的填充方案有12种；还有 n = 8特有的不可分割的填充方案，如下图。将所有方案相加得n = 8的填充方案有153种。

由上述各图可以看出，当n > 2时, 每个F[n]都有两个自己的特有不可分割的填充方法。都是先铺一层横着的1 * 2的方块，然后在最左和最右边各放一个竖着的1 * 2的方块。剩下的空间全用横着的1 * 2方块填充。然后上下颠倒变成不同的填充方案。

为什么不可分割?

从n > 2的图中可以看出不管如何分割都无法分割出被完整的1 * 2方块填充的子区域。

代码：

#include <iostream>
using namespace std;
int DP(int N);
int m[64] = {0};
int main(void)
{
    int N;
    for(cin >> N; N != -1; cin >> N)
    {
        if(N % 2 != 0)
            cout << 0 << endl;
        else
            cout << DP(N) << endl;
    }
    return 0;
}
int DP(int N)
{
    int ans = 0;
    int temp = 0;
    if(m[N] != 0)
        return m[N];
    if(N <= 0)
        return 1;
    for(int i = 2; i <= N; i += 2)
    {
        temp = DP(N - i);
        if(i == 2)
            ans += 3 * temp;
        else
            ans += 2 * temp;
    }
    return ans;
}

数学递推公式

由动态规划法分析过程可以推得：

f(n)=f(n-2)*3+f(n-4)*2+…+f(2)*2+f(0)*2 ---- 表达式1

f(n-2)=f(n-4)*3+f(n-6)*2+…+f(2)*2+f(0)*2 ---- 表达式2

表达式1减去表达式2得：

f(n)=4*f(n-2)-f(n-4)