算法（10）矩形覆盖

题目描述

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

看到这个题感觉有点熟悉啊，仔细一想不正是跳台阶的问题吗？一次一个或者两个，这个本质也是啊。一个的相当于竖着的，两个的相当于横着放。

具体可以参照跳台阶。

递归方法

 public static int JumpFloor(int target) {
        //最后没有了
        if (target == 0) {
            return 0;
        }
        //最后剩一个
        if (target == 1) {
            return 1;
        }
        //最后剩两个
        if (target == 2) {
            return 2;
        }

        return JumpFloor(--target) + JumpFloor(--target);

    }

for循环方法

 public static int JumpFloor1(int target) {
        //最后没有了
        if (target == 0) {
            return 0;
        }
        //最后剩一个
        if (target == 1) {
            return 1;
        }
        //最后剩两个
        if (target == 2) {
            return 2;
        }
        
        int one = 1;
        int two = 2;
        int result = 0;
        for (int i = 2; i < target; i++) {
            result = one + two;
            one = two;
            two = result;
        }
        return result;
        
    }