剑指offer之矩形覆盖
矩形覆盖
https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=13&&tqId=11163&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
题目
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形,总共有多少种方法?
比如n=3时,23的矩形块有3种覆盖方法:
思路
本题其实和跳台阶的题很像,当最后一个小矩形是竖着放时,就是f(n-1)种方法,当横着放时,另一个也得横着放,所以就是f(n-2)种方法。需要注意的是,递归时候要注意方法,直接调用会内存超限,所以最好是多写点代码,累加。
代码
class Solution { public: int rectCover(int number) { int res = 0; int per1 = 1, per2 = 2; if (1 == number ) { return number; } else if (2 == number) { return number; } else { for (int i = 3; i <= number; i++) { res = per1 + per2; per1 = per2; per2 = res; } } return res; } };