算法设计------Dynamic Pragraming Tri Tiling

发表于 | 分类于

问题描述

用1 x 2的骨牌放满3 x n的矩形有多少种方法

例如：下面是铺满3 x 12的一个方法

问题分析

用dp[n]表示放满前n列的方案数

  • n为奇数时显然没有合法方案

  • n为偶数时考虑最右边一个分割线的位置，那么这个位置只可能取n-2,n-4,…,2

    1. 该位置为n-2时，右边两列有三种放法，
    2. 该位置取其他值时，若要保证m列中没有分割线只有两种放法（m=4时如下图）

据此可得递推方程：
dp[n]=3 x dp[n-2]+2 x (dp[n-4]+dp[n-6]+…+dp[2])
同理有dp[n-2]=3 x dp[n-4]+2 x (dp[n-6]+dp[n-8]+…+dp[2])
两式做差得dp[n]=4 x dp[n-2]-dp[n-4]，之后以dp[0]=1,dp[2]=3为起点递推即可

Coding

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
int tri_Tiling (int n){
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 1) {
        return 0;
    }
    if (n == 2) {
        return 3;
    }

    return 4 * tri_Tiling(n - 2) - tri_Tiling(n - 4);
}

时间复杂度

时间复杂度为O(n)

测试代码

1
2
3
4
5
6
int tri_Count = tri_Tiling(3);
printf("tri_Count_3 == %d\n",tri_Count);
tri_Count = tri_Tiling(8);
printf("tri_Count_8 == %d\n",tri_Count);
tri_Count = tri_Tiling(12);
printf("tri_Count_12 == %d\n",tri_Count);

执行结果

1
2
3
tri_Count_3 == 0
tri_Count_8 == 153
tri_Count_12 == 2131

相关链接

Tiling Problem

如果对你有帮助的话，Star✨下一吧！