题目
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
1.思路
宏观分析
依然是斐波那契数量问题的变形题。
先把2 * n 的覆盖方法记作F(n)。用第一个2×1的小矩形去覆盖大矩形的左上角时，有两种选择：横着或者竖着。竖着放的时候，其右侧还剩2 × (n - 1)大小的区域，这种状态下的覆盖方法记作F(n - 1)，若第一块是横着放在，那么左下角必须放一个2 × 1 的小矩阵，此时整体还剩2 × (n - 2) 大小的区域，这种状态下的覆盖方法记作F(n - 2)。因此可以推到出，F(n) = F(n - 1) + F(n - 2)，即这是一道斐波那契数列的变形题。
（1）递归
①n <= 0 时，F(n) = 0；
②n = 1 时，F(n) = 1 – > 只有一种摆放的方法；
③n = 2 时，F(n) = 2 – > 有两种摆放的方法，两个矩形都横着，或者都竖着，都能满足铺满2 × 2的大矩形的需求；
④n > 2 时，F(n) = F(n - 1) + F(n - 2)。
（2）非递归（借助数组）效率高
①n <= 0 时，返回0；
②n = 1 时，返回1 – > 只有一种摆放的方法；
③n = 2 时，返回2 – > 有两种摆放的方法，两个矩形都横着，或者都竖着，都能满足铺满2 × 2的大矩形的需求；
④n > 2 时，用空间换时间，创建一个大小为n的数组dp[n]，初始化
dp[0] = 1; dp[1] = 2; 那么当n大于2时，使用一个次数为n - 2 的循环，记录全部的递推中间值，并将最后的dp[n - 1]返回即可，斐波那契数列本身就是递推关系定义的。
2.代码（Java实现）
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 {
// 方法1：递归
// return RectCover(target-1)+RectCover(target-2);
// 方法2：非递归
int[] dp = new int[target];
dp[0] = 1;
dp[1] = 2;
for (int i = 2; i < target; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[target - 1];
}
}
}PS：斐波那契数列问题就全部做完啦，拖了好久终于把这几个题的博客写完了。
斐波那契数列所有题目的Java解题代码都可以在 我的主页 里找到，如果有不对的地方欢迎各位批评指正，感谢！
本文链接： https://hexo.whtli.cn/archives/ce61152f.html
版权声明： 遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。