【剑指Offer】010——覆盖矩阵（递归）

题目描述

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

解题思路

image

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

参考代码

Java

public class Solution {
        public int RectCover(int target) {
            if (target <= 2)
                return target;
            int fn1 = 1, fn2 = 2;
            for (int i = 3; i <= target; i++) {
                fn2 = fn1 + fn2;
                fn1 = fn2 - fn1;
            }
            return fn2;
        }
    }

Python

class Solution:
    def rectCover(self, number):
        if number <= 2: return number
        fn1,fn2=1,2
        for i in range(3,number+1):
            fn2 = fn1 + fn2
            fn1 = fn2 - fn1
        return fn2

个人订阅号

image