剑指Offer面试题：13.矩形覆盖

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

————————————————
二、思路
————————————————
当 n 为 1 时，只有一种覆盖方法：

————————————————
当 n 为 2 时，有两种覆盖方法：

————————————————
要覆盖 2n 的大矩形，可以先覆盖 21 的矩形，再覆盖 2(n-1) 的矩形；或者先覆盖 22 的矩形，再覆盖 2(n-2) 的矩形。而覆盖 2(n-1) 和 2(n-2) 的矩形可以看成子问题。该问题的递推公式如下：

————————————————
三、解决问题
————————————————

package swordoffer;

/**
 * @author LQ
 * @version 1.0
 * @date 2020-03-15 20:36
 */

/**
 * 我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。
 * 请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？
 */
public class Solution13 {
    public static void main(String[] args) {
        Solution13 demo = new Solution13();
        System.out.println(demo.RectCover(1));
        System.out.println(demo.RectCover(2));
        System.out.println(demo.RectCover(8));
        System.out.println(demo.RectCover(0));
    }
    public int RectCover(int target) {
        if(target < 1){
            //当target<0,不符合约束条件
            throw new RuntimeException("下标错误,应从1开始！");
        }
        if(target <= 2){//当target=1,target=2
            return target;
        }
        int pre2 = 1, pre1 = 2;
        int result = 0;
        for (int i = 3; i <= target; i++) {
            result = pre2 + pre1;//f(n)= f(n-2) + f(n-1) 3=1+2
            pre2 = pre1;//1=2
            pre1 = result;//2=3
        }
        return result;
    }
}

————————————————

————————————————
努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。