剑指offer-10、矩阵覆盖
题目描述我们可以用 2 * 1 的小矩形横着或者竖着去覆盖更大的矩形。请问用n个 2 * 1 的小矩形无重叠地覆盖一个2 * n的大矩形，总共有多少种方法？
比如n=3时，2 * 3 的矩形块有3种覆盖方法：
思路及解答
我们需要用若干个2×1的小矩形（可以横放或竖放）无重叠地覆盖一个2×n的大矩形，求总共有多少种不同的覆盖方法。例如当n=3时，共有3种覆盖方法。
通过观察小规模案例，我们可以发现：
[*]n=1时，只有1种方法（竖放）
[*]n=2时，有2种方法（两个竖放或两个横放）
[*]n=3时，有3种方法
[*]n=4时，有5种方法
显然，这形成了一个类似斐波那契数列的规律：f(n) = f(n-1) + f(n-2)。这一题其实和上面青蛙跳台阶和斐波那契数列是一样的，变的只是场景。
递归
递归是解决这类问题最直观的方法。对于2×n的矩形，我们考虑第一块小矩形的放置方式：
[*]如果竖着放，则剩下的部分是2×(n-1)的矩形，有f(n-1)种方法
[*]如果横着放，则下方也必须横放一块，剩下的部分是2×(n-2)的矩形，有f(n-2)种方法
因此，总方法数为这两种情况之和：f(n) = f(n-1) + f(n-2)，这正是斐波那契数列的递推关系
public class Solution { public int rectCover(int n) { if (n 前排留名，哈哈哈 谢谢分享，辛苦了 收藏一下 不知道什么时候能用到 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 这个有用。 热心回复！ 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 不错，里面软件多更新就更好了 感谢分享，下载保存了，貌似很强大 感谢分享，下载保存了，貌似很强大 感谢，下载保存了 谢谢分享，试用一下 很好很强大我过来先占个楼 待编辑 感谢分享 谢谢楼主提供！ 前排留名，哈哈哈 这个有用。 yyds。多谢分享 感谢，下载保存了
页:
[1]
2