0%

矩形覆盖

发表于 更新于

我们可以用2×12\times 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2×12\times 1的小矩形无重叠地覆盖一个2×n2\times n的大矩形，总共有多少种方法？

令2×n2\times n的大矩形可以用dp[n]个小矩形覆盖，而2×n2\times n的大矩形有2×(n−1)2\times (n-1)的大矩形和一个小矩形，以及2×(n−2)2\times (n-2)的大矩形和2个小矩形覆盖，共2种情况，故

dp[n]=dp[n−1]+dp[n−2]dp[n]=dp[n-1]+dp[n-2]

类比斐波那契数列和跳台阶，有令

A=[1110]A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}

有

[dp[n+1]dp[n]00]=[dp[n]dp[n−1]00]×A\begin{bmatrix} dp[n+1] & dp[n] \\ 0 & 0 \\ \end{bmatrix} = \begin{bmatrix} dp[n] & dp[n-1] \\ 0 & 0 \\ \end{bmatrix} \times A

而

[dp[2]dp[1]00]=[2100]\begin{bmatrix} dp[2] & dp[1] \\ 0 & 0 \\ \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 0 & 0 \\ \end{bmatrix}

故

[dp[n+1]dp[n]00]=[2100]×An−1=[2100]×A⌊n−12⌋×A(n−1)%2\begin{bmatrix} dp[n+1] & dp[n] \\ 0 & 0 \\ \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 0 & 0 \\ \end{bmatrix} \times A^{n-1} = \begin{bmatrix} 2 & 1 \\ 0 & 0 \\ \end{bmatrix} \times A^{\lfloor \frac{n-1}{2} \rfloor} \times A^{(n-1) \% 2} 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int base[4] = {1, 1, 1, 0}, a_n[4] = {1, 1, 1, 0};
    void times(int a[4], int b[4])
    {
        int r[4] = {
            a[0] * b[0] + a[1] * b[2],
            a[0] * b[1] + a[1] * b[3],
            a[2] * b[0] + a[3] * b[2],
            a[2] * b[1] + a[3] * b[3]};
        a[0] = r[0];
        a[1] = r[1];
        a[2] = r[2];
        a[3] = r[3];
    }
    void cal_a(int n)
    {
        if (n > 1)
        {
            n -= 2;
            while (n)
            {
                if (n & 1)
                {
                    times(a_n, base);
                }
                times(base, base);
                n >>= 1;
            }
        }
    }
    int rectCover(int n)
    {
        if (n <= 2)
        {
            return n;
        }
        else
        {
            int m[4] = {2, 1, 0, 0};
            cal_a(n - 1);
            times(m, a_n);
            return m[0];
        }
    }
};