题目描述

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

解题方法

此题明显的为动态规划思维，找寻三个条件：最优子结构，状态转移方程和边界条件
1. 我们假设长为n宽为的矩阵结果是F(n,2)，那么我们要得到F(n,2)此时可以将1*2的矩形竖着
放，如下面的可能2所示，同时也可能是横着放(因为高度只有2，横着放只有一种叠加覆盖)，
如下面的可能1所示，那么F(n, 2) = F(n-1, 2) + F(n-2, 2)
2. 通过上面的方程可以得出这个状态转移和高度无关（主要是因为高度为2，横着放之后后面只能横着放覆盖了），那么我们可以简化为F(n) = F(n-1) + F(n-2),斐波拉契数列
3. 寻找这个斐波拉契数列的边界值，当n=1时，此时只能竖着放，那么就是F(1) = 1, 当n=2时，那么有两种可能，竖着或者横着，那么F(2)=2
4. 累加的方式求解F(n)即可

JAVA源代码

public class Solution {
    public int RectCover(int target) {
        int[] result = new int[target+1];
        if (target==0) return 0;
        if (target==1) return 1;
        if (target==2) return 2;
        result[0] =0;
        result[1] = 1;
        result[2] = 2;
        for (int i=3; i<=target; i++) {
            result[i] = result[i-1] + result[i-2];
        }
        return result[target];
    }
}