剑指offer 矩形覆盖

╰+哭是因爲堅強的太久メ 2024-04-18 09:57 80阅读 0赞

# [剑指offer题型分类及各题的解题思路与代码（<---点我跳转  ^ - ^）][offer_---_ _ -] #

## 1、题目描述 ##

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

### 2、初始结构如下 ###

class Solution {
    public:
        int rectCover(int number) {
    
        }
    };

### 3、分析 ###

我们先把2\*8的覆盖方法记为f(8)。用第一次2\*1的小矩形去覆盖大矩形的最左边时有两种选择：竖着放或者横着放。当竖着放的时候，右边还剩下2\*7的区域，这种情形下的覆盖方法记为f(7)。接下来考虑横着放的情况。当2\*1的小矩形横着放在左上角的时候，左下角必须和横着放一个2\*1的小矩形，而在右边还剩下2\*6的区域，这种情形下的覆盖方法记为f(6)，因此f(8) = f(7) + f(6)。此时我们可以看出，这仍然是斐波那契数列。

### 4、C++实现代码如下 ###

class Solution {
    public:
        int rectCover(int number) 
        {
            if(number < 0)
                return -1;
            
            if(number == 1 || number == 2)
                return number;
            
             //标记根节点的右结点的值
            int right = 1;
            //标记根节点的左节点的值
            int left = 0;
            //标记根节点的值
            int root = 0;
            //从第二项开始，向n迭代，x2 = x1 + x0,...xn = x(n-1) + x(n-2)
            for(int i = 1; i <= number; ++i)
            {
                root = left + right;
                
                left = right;
                right = root;
            }
            return root;
        }
    };

[offer_---_ _ -]: https://blog.csdn.net/qq_26079093/article/details/96605538