矩形覆盖

public class Solution {
    //解题思路：
    //动态规划的题，基本都可以将前5个画出来，然后找规律
    //n = 1, 1种方法
    //n = 2, 2种方法
    //n = 3, 3种方法
    //n = 4, 4种方法
    //n = 5, 5种方法
    //可得出规律：rectCover(n) = rectCover(n-1) + rectCover(n -2)
    //解法一：递归
    public int rectCover(int target) {
        if(target <= 2) {
            return target;
        }
        return rectCover(target-1) + rectCover(target-2);
    }
    
    
    //解法二：优化递归存储
    public int rectCover(int target) {
        if(target <= 2) {
            return target;
        }
        int one =1;
        int two =2;
        for(int i = 3; i<= target; i ++) {
            two = one + two;
            one = two - one;
        }
        return two;
    }
}