开发者社区云计算文章正文

剑指offer_递归与循环---矩形覆盖

2023-06-17 80

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 剑指offer_递归与循环---矩形覆盖

##题目描述

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形，总共有多少种方法？
##解题思路
依旧是斐波那契数列
2n的大矩形，和n个21的小矩形
其中target2为大矩阵的大小

有以下几种情形：

1⃣target <= 0 大矩形为<= 20,直接return 1；
2⃣️target = 1大矩形为21，只有一种摆放方法，return1；

3⃣️target = 2 大矩形为2*2，有两种摆放方法，return2；

4⃣️target = n 分为两步考虑：

##代码实现

/**
 * 
 */
package 递归和循环;
/**
 * <p>
 * Title:RectCover
 * </p>
 * <p>
 * Description:
 * </p>
 * 
 * @author 田茂林
 * @data 2017年8月23日 下午12:00:44
 */
public class RectCover {
  public int IntRectCover(int target) {
    if(target==1){
      return 1;
    }
    if(target==2){
      return 2;
    }
    int num =0;
    if(target>2){
      num = IntRectCover(target-1)+IntRectCover(target-2);
    }
    return num;
  }
}