题解 | #矩形覆盖#
矩形覆盖
http://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6
算法思想一：迭代
解题思路：
图示：
分析从n=3到n=4，有2种情况：
1、直接在n=3的情况下，再后面中添加一个竖着的。这个很显然成立，有3种情况
2、然后横着的显然能添加到n-2的情况上，也就是在n=2后面，添加2个横着的。有2种情况
总结以上规律发现 fn 表示覆盖矩形的方法数，则 fn(n) = fn(n-1) + fn(n-2)
1、直接在n=3的情况下，再后面中添加一个竖着的。这个很显然成立，有3种情况
2、然后横着的显然能添加到n-2的情况上，也就是在n=2后面，添加2个横着的。有2种情况
总结以上规律发现 fn 表示覆盖矩形的方法数，则 fn(n) = fn(n-1) + fn(n-2)
因此可以想到采用迭代的方式计算：
1、初始化：a = 1, b = 2
2、循环计算：fn = a + b, a = b, b = fn
3、返回fn
代码展示：
Python版本
class Solution: def rectCover(self, number): # write code here # 特殊情况 if number <= 2: return number # 初始化 a = 1 b = 2 # 循环计算 for i in range(3, number+1): fn = a + b a = b b = fn return fn
复杂度分析
时间复杂度)
：N表示number，循环计算次数
空间复杂度)
：仅使用多个常数级变量空间
算法思想二：递归
解题思路：
由方法一可知：%20%3D%20fn(n-1)%20%2B%20fn(n-2))
所以采用递归的方式计算fn(n)，将计算fn(n)分为两个步骤 fn(n-1) 和 fn(n-2)，然后依次往下递归计算
代码展示：
JAVA版本
public class Solution {
public int rectCover(int target) {
// 特殊情况
if (target <= 2){
return target;
}else{
// 递归
return rectCover(target - 1) + rectCover(target - 2);
}
}
} 复杂度分析
时间复杂度：N表示number，递归计算次数
空间复杂度：递归算法中使用了栈空间
