剑指offer(C++)-JZ70:矩形覆盖-创新互联
作者:翟天保Steven
版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处
我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形,从同一个方向看总共有多少种不同的方法?
数据范围:0≤n≤38
进阶:空间复杂度 O(1) ,时间复杂度O(n)
注意:约定 n == 0 时,输出 0
比如n=3时,2*3的矩形块有3种不同的覆盖方法(从同一个方向看):
输入描述:2*1的小矩形的总个数n
返回值描述:覆盖一个2*n的大矩形总共有多少种不同的方法(从同一个方向看)
示例:输入:
4
返回值:
5解题思路:
本题是类似青蛙跳台阶的题目,本质上是一个数学问题。
假设2*(n)矩形的覆盖方案数量是f(n),则2*(n)的大矩形有两种组合形式。2*(n-1)的大矩形加1块竖直的矩形是一种情况,2*(n-2)的大矩形加两块横放叠加的矩形是一种情况,所以f(n)=f(n-1)+f(n-2),显然是斐波那契数列了,用动态规划的解法即可。
测试代码:class Solution {
public:
int rectCover(int number) {
// 当n为0、1、2时,可能的情况数量刚好和n一致
if(number<= 2)
return number;
// 初始化
int a = 1;
int b = 2;
int c = 0;
// 斐波那契数列遍历
for(int i = 3; i<= number; ++i)
{
c = a + b;
a = b;
b = c;
}
return c;
}
};
常规跳台阶问题可以参考:
剑指offer(C++)-JZ69:跳台阶(算法-动态规划)_翟天保Steven的博客-博客
该文章中提供了4种递优的解法,以帮助大家更好地理解动态规划。但该4种解法中最优解的时间复杂度也要O(n),因此我又探究了如何实现O(logn)的解法,将问题转换为矩阵求解的形式,运用快速幂的方法实现了高次幂的快速求解,达到了O(logn)水平。参考文章如下:
剑指offer(C++)-JZ10:斐波那契数列(时间复杂度O(logn)解法)_翟天保Steven的博客-博客
以上两篇文章都是解决斐波那契数列问题的相关内容,希望能对你有一些帮助。
推荐电影——消失的她!
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
新闻名称:剑指offer(C++)-JZ70:矩形覆盖-创新互联
标题网址:http://myzitong.com/article/hghhe.html