题目描述

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

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

答案

public class Solution {
    public int RectCover(int target) {
        if(target<=3)return target;
        int [] f = new int[target+1];
        f[0] = 0;
        f[1] = 1;
        f[2] = 2;
        f[3] = 3;
        int t = 4;
        while(t<=target){
            f[t] = f[t-1]+f[t-2];
            t++;
        }
        return f[t-1];
    }
}

解析

这道题最难的部分在于思路,只要没有思路的时候我们就从小到大进行思考。
对于n=1,显然只有一种情况

对于n=2, 显然有两种情况

对于n=3

对于n=4,

我们主要需要思考,n=4是怎么来的?能不能从n=3中得到?

显然是可以的,我们在n=3的情况下,在最后面加一个竖直的条,可以得到3种情况。

接下来我们考虑增加横向条的情况,因为是2X1的长方形,所以我们需要两个长条横放,保证大长方形的宽度为2。

所以我们要在n=2的情况加两个长方形。

所以n=4的情况等于n=3和n=2的情况的和。

推导出f(n) = f(n-1)+f(n-2)


醉后不知天在水,满船清梦压星河