矩形覆盖

题目描述

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

思路

由于小矩形的尺寸是2×1，所以有大矩形为2×n的存在，那么我们第一步就可以有两种处理方式：

• 第一步如果选择竖方向填充，那么该问题的规模就缩减为对于剩余的2*(n-1)的大矩形的填充 ；
• 第一步如果选择横方向的填充，则第二排的前面两个小矩形也只能如此填充，那么该问题的规模就缩减为对于剩余的2*(n-2)的大矩形的填充 。
• 结合上述分析，很容易得到递推的关系： rectCover(n) = rectCover(n-1)+rectCover(n-2)。当然此处也要注意递归跳出条件的判定 。

public int rectCover(int n){
    if(n<=2)
        return n;
    int ret1 = 1;
    int ret2 = 2;
    int ret = 1;
    for(int i=3; i<=n; i++){
        ret = ret1 + ret2;
        ret1 = ret2;
        ret2 = ret;
    }
    return ret;
}