矩形覆盖
题目描述
我们可以用2 × 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2×1的小矩形无重叠地覆盖一个2 × n的大矩形，总共有多少种方法？
解题思路
与青蛙跳台阶类似。假设我们从左上角开始覆盖，放置第一个矩形有两种情况，竖着放与横着放。竖着放的情况，剩下一个2 × (n - 1)的矩形需要覆盖。横着放的情况，右下角只能同样覆盖一个横着放的矩形，然后剩下一个2 × (n - 2)的矩形需要覆盖。得到$f(n) = f(n - 1) + f(n - 2)$，同斐波那契数列
代码
public class Solution {
public int rectCover(int target) {
if(target <= 0) {
return 0;
} else if(target == 1) {
return 1;
} else if(target == 2) {
return 2;
} else {
int number1 = 1;
int number2 = 2;
for(int i = 0; i < target - 2; i++) {
int sum = number1 + number2;
number1 = number2;
number2 = sum;
}
return number2;
}
}
}
PREVIOUS剑指Offer 面试题09-3：变态跳台阶