【剑指offer】10:矩形覆盖
2024-08-28 02:01:41
题目描述:
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
解题思路:
①方法一
对于这种题没有思路怎么办?可以先从最简单的情况开始考虑:
显然,当n = 1时,只有一种方法
当n = 2时,如图有两种方法
当n = 3时,如图有三种方法
当我们做到这里总会出现错觉,是不是n等于几就是有几种方法呢?我们再接着来尝试:
当n = 4时,如图有五种方法。
做到这里基本上会确定就是斐波拉契数列了,可以接着验证,这里不做赘述
②方法二
可以先把2X4的覆盖方法记为f(4)【如上图n=4时的第一个图】,用1X2的小矩形去覆盖时,有两种选择:横着放或者竖着放。当竖着放时,右边还剩下2X3的区域。很明显这种情况下覆盖方法为f(3)。当横着放时,1X2的矩形放在左上角,其下方区域只能也横着放一个矩形,此时右边区域值剩下2X2的区域,这种情况下覆盖方法为f(2)。所以可以得到:f(4)=f(3)+f(2),不难看出这仍然是斐波那契数列。
特殊情况:f(1)=1,f(2)=2
代码实现
(C实现):
int rectCover(number)
{
// write code here
int fir = 1, sec = 2, res;
if (number <= 0 || number == 1 || number == 2) return number;
for (int i = 2; i <number; i++) {
res = fir + sec;
fir = sec;
sec = res;
}
//res = rectCover(number - 1) + rectCover(number - 2); 递归方式
return res;
}
(JavaScript实现):
function rectCover(number)
{
// write code here
var fir = 1, sec = 2, res;
if (number <= 0 || number == 1 || number == 2) {
return number;
}
for (var i = 2; i <number; i++) {
res = fir + sec;
fir = sec;
sec = res;
}
//res = rectCover(number - 1) + rectCover(number - 2); 递归方式
return res;
}
最新文章
- cocos2d-x 3.10 PageView BUG
- Maven 常用的命令
- vim operation
- StackOverflow程序员推荐的几本书籍
- 软件开发过程中的审查 (Review)
- DI 之 3.2 循环依赖 (伍)
- 使用 CUDA 进行计算优化的两种思路
- samba配置只读共享
- 001 The Hello World In Csharp
- 前后端分离--mock
- poj 3045 Cow Acrobats(二分搜索?)
- String类使用方法
- 关于easyUI的datebox加失去焦点事件即click、blur等
- C语言_结构体的4种定义初始化方式及案例
- 【iOS】swift 74个Swift标准库函数
- [jQuery]循环遍历改变a标签的href
- Spark学习之常用算子介绍
- ES6必知必会 (四)—— Symbol、Set和Map
- RobotFramework基本用法(二)
- manjaro 添加tash 快捷方式