本文为剑指 offer 系列第十二篇。
主要知识点为斐波那契数列，只是需要先对问题进行分析，同样还是用三种方式来解决这个问题。
我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形，总共有多少种方法？
解题思路
方便解释起见，我们假设整个横着的就是一个宽为2，长为n的大矩形，下面分情况讨论。
- n = 0 : 结果为0
- n = 1 : 结果为1，竖着一个。
- n = 2 : 结果为2 竖着两个或者横着两个。
- n = 3 : 结果为3，在n=1的基础上横排两个，或者在n=2的基础上竖着加一个。
- ……
综上，我们就得到结论：f(n) = f(n-1)+f(n-2) 初始项为{0,1,2}
思路1
直接用递归。
思路2
用数组保存
思路3
保存两个关键数字。
解题代码
思路1代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int rectCover(int n) {
// 方法1 直接用递归。
if(n == 0){
return 0;
}else if(n == 1){
return 1;
}else if(n == 2){
return 2;
}else{
return rectCover(n-1)+rectCover(n-2);
}
}
};
|
时间复杂度为O(n^2),空间复杂度为O(n)
思路2代码
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
int rectCover(int n) {
//方法2: 数组保存
vector<int> res = {0,1,2};
for(int i = 2;i < n; i++){
res.push_back(res[i]+res[i-1]);
}
return res[n];
}
};
|
时间复杂度为O(n),空间复杂度为O(n)
思路3代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int rectCover(int n) {
// 方法3. 用两个关键变量进行保存。
if(n==0) return 0;
if(n == 1) return 1;
if(n == 2) return 2;
int first = 1,second = 2;
for(int i = 2; i < n; i++){
int temp = first+second;
first = second;
second = temp;
}
return second;
}
};
|
时间复杂度为O(n),空间复杂度为O(1)
以上，本题结束！