剑指offer10.2 矩形覆盖

Problem:

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

Intuition:

这个问题就是一个地地道道的斐波那契数列的问题，但是因为隐藏的比较深，看题的时候可能第一时间没办法发现这个事实。不过我们可以做到的是看到这个题第一时间反应过来这是一个递归的问题。我们可以轻易发现n=1时只有一种摆法，n=2时只有两种摆法。如果n>2,那么我们考虑整个图形的左上角。如果左上角的矩形是竖着摆的，那么这种情况就是f(n-1).如果左上角的矩形时横着摆的（21），那么我们可以发现它的下面也必须是一个横着摆的矩形。这样上下两个矩形一起就会拼成一个22的矩形，那么这种情况就是f(n-2)。鉴于左上角的矩形只有两种摆法情况（横着摆或者竖着摆），所以这个问题就被完全转化成了一个斐波那契数列的问题。

Solution:

public int RectCover(int n) {
    if (n <= 2)
        return n;
    int pre2 = 1, pre1 = 2;
    int result = 0;
    for (int i = 3; i <= n; i++) {
        result = pre2 + pre1;
        pre2 = pre1;
        pre1 = result;
    }
    return result;
}