剑指Offer（十）--矩形覆盖
- 题目描述
- 思路以及解法
题目描述
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
比如n=3时，2*3的矩形块有3种覆盖方法：
思路以及解法
这道题最基本的是要分析简单的情况，所有的复杂都是由最最简单的东西组成的，不要一看到n就觉得很难，假设n是1或者是2，是3，会不会只有几种情况呢？相信我们平时解决问题也是如此。
先说思路，基本是递归，首先如果n为1，那么肯定只有一种，f(1)=1,如果n=2，f(2)=2
但是n>2的时候呢？那么我们的思路就可以分为第一次切分长度为1，和切分长度为2来计算，也就是剩下的是f(n-1)和f(n-2)，两者加起来即可。
递归写法代码如下：
public class Solution {
public int RectCover(int target) {
if(target<=0){
return 0;
}else if(target==1){
return 1;
}else if(target==2){
return 2;
}else {
return RectCover(target-1)+RectCover(target-2);
}
}
}
如果我不想使用递归呢？那么直接不断地把前面两个数加起来赋值给当前的数字即可。
public class Solution {
public int RectCover(int target) {
if (target <= 0) {
return 0;
} else if (target < 3) {
return target;
} else {
int num1 = 1;
int num2 = 2;
int result = 0;
for (int i = 3; i <= target; i++) {
result = num1 + num2;
num1 = num2;
num2 = result;
}
return result;
}
}
}
- END -
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-09-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
