我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？
首先来理解一下题意，比如 n = 3 时，2*3 的矩形块有三种覆盖方法：
这道题目依旧是斐波那契数列，2*n 的大矩形，和 n 个 2*1 的小矩形，其中 target*2 为大矩阵的大小，有以下几种情形：
-
target <= 0
大矩形为 <= 2*0，直接 return 1
-
target = 1
大矩形为 2*1，只有一种摆放方法，return 1
-
target = 2
大矩形为 2*2，有两种摆放方法，return 2
-
target = n
分为两步考虑：
-
第一次摆放一块 2*1 的小矩阵，则摆放方法总共 f(target - 1)
-
第一次摆放一块 1*2 的小矩阵，则摆放方法总共为 f(target - 2)，因为摆放了一块 1*2 的小矩阵，对应下方的 1*2 摆放方法就确定了，所以为 f(target - 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 {
return RectCover(target - 1) + RectCover(target - 2);
}
}
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
