剑指Offer第十题：矩阵覆盖

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

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

解答：
思想：和跳台阶类似，小矩形竖着放相当于跳一级台阶，横着放相当于跳两级台阶，所以可以复用跳台阶的代码（见第八题）。

public class Q_9 {

public int JumpFloorII(int target) {
    int sum = 1;
    for (int i = 1; i < target; i++) {
        sum += JumpFloorII(i);
    }
    return sum;
}

public static void main(String[] args) {
    System.out.println(new Q_9().JumpFloorII(5));
}

}
-------------2020/4/19------------
记忆化搜索和动态规划更优