10. 矩形覆盖
题目描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
解题思路：
这仍然是一个斐波那契数列问题。
f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2)
解答：
class Solution {
public:
int rectCover(int number) {
if(number <= 0)
return 0;
if(number == 1)
return 1;
int first = 1, second = 2, third = 2;
for(int i = 2; i < number; ++i)
{
third = first + second;
first = second;
second = third;
}
return third;
}
};
大家有兴趣可以访问我的个人博客，不定时更新一些内容哦！
图片来自必应壁纸
网友评论