题目描述

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

牛客网在线测试

解题思路

当n为1时，只有一种覆盖方法；当n为2 时，有两种覆盖方法；可以先覆盖 2*1 的矩形，再覆盖 2*(n-1) 的矩形；或者先覆盖 2*2 的矩形，再覆盖 2*(n-2)
的矩形。而覆盖 2*(n-1) 和 2*(n-2) 的矩形可以看成子问题。

GE4hUs.png

解题代码

  1. 递归写法
1
2
3
4
5
6
public int RectCover(int target) {
        if(target<=2){
            return target;
        }
        return RectCover(target-1)+RectCover(target-2);
    }
  1. 非递归写法
1
2
3
4
5
6
7
8
9
10
11
12
13
public int RectCover(int n) {
        if (n <= 2) {
            return n;
        }
        int pre2 = 1, pre1 = 2;
        int result = 0;
        for (int i = 3; i <= n; i++) {
            result = pre2 + pre1;
            pre2 = pre1;
            pre1 = result;
        } 
        return result;
    }
技术Java算法
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~