剑指offer（十）矩形覆盖

点击进入 牛客网题库：矩形覆盖

题目描述

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

比如n=3时，2*3的矩形块有3种覆盖方法：

6384065_1581999858239_64E40A35BE277D7E7C87D4DCF588BE84.png

方法一 递归

public class Solution {
   /**
   * 这个是切割就拿最后一个砖可以的情况
   * 就是最后一个砖放 2块砖，或者放一块砖
   * 所以推出 f(n) = f(n-1) + f(n-2) 这种子问题
   *
   */
   public int RectCover(int target) {
       if(target == 0) {
           return 0;
       }
       if(target == 1) {
           return 1;
       }
       if(target == 2) {
           return 2;
       }
       
       return RectCover(target-1)+ RectCover(target-2);
   }
}

方法二 迭代

public class Solution {
    /**
    * 这个是切割就拿最后一个砖可以的情况
    * 就是最后一个砖放 2块砖，或者放一块砖
    * 所以推出 f(n) = f(n-1) + f(n-2) 这种子问题
    *
    */
    public int RectCover(int target) {
        if(target == 0) {
            return 0;
        }
        if(target == 1) {
            return 1;
        }
        if(target == 2) {
            return 2;
        }
           
        int first = 1;
        int second = 2;
        int result = 0;
        
        for(int i = 3; i <= target; i++ ) {
            result = first + second;
            int tmp = first;
            first = second;
            second = tmp + second;
        }
        
        return result;
    }
}