题目链接

牛客网

题目描述

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

该问题的递推公式如下：
image.png

  1. class Solution {
  2. public:
  3.     int rectCover(int number) {
  4.         if(number<3)
  5.             return number;
  6.         int a1=1,a2=2,tmp;
  7.         for(int i=2;i<number;i++){
  8.             tmp = a2;
  9.             a2 = a1+a2;
  10.             a1 = tmp;
  11.         }
  12.         return a2;
  13.     }
  14. };
  15. //递归法，不推荐 耗时长
  16. class Solution {
  17. public:
  18.     int rectCover(int number) {
  19.         if(number < 3)
  20.             return number;
  21.         return rectCover(number - 2)+rectCover(number - 1);
  22.     }
  23. };
  • 时间复杂度：O(N)
  • 空间复杂度：O(1)