Sword to Offer-10.2 矩形覆盖 ❀

  • 题目描述:我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n2 * 1的小矩形无重叠地覆盖一个2 * n的大矩形,总共有多少种方法?

  • 比如n = 3时,2 * 3的矩形块有3种覆盖方法:

解题思路:

1、关键在于理解为什么这是斐波那契问题;
2、当n=1时,只有一种摆放方法,当n=2时,有两种摆放方法;
3、当n=3时,
(1)假设第一块竖放,那么接下来是一个n=2摆放问题,已知有两种摆放方法;
(2)假设第一块横放,那么其下面那块区域必须同样横放一个2*n的矩阵,这是第一块横放情况下确定的,所以接下来是一个n=1摆放问题,已知有一种摆放方法;
(3)第一块横放或者竖放已经包含了第一块所有可能的摆放方式,因而f(3)=f(2)+f(1);
4、当n>3时,情况也如此,f(n)=f(n-1)+f(n-2)

问题图解:

AC代码:

// Cover a 2*n Rectangle with 2*1 Rectangle

public class Solution {
    public int RectCover(int target) {
        if (target <= 1) {
            return target;
        }
        int[] method = new int[target+1];
        method[1] = 1;
        method[2] = 2;
        for (int i=3; i<=target; i++) {
            method[i] = method[i-1] + method[i-2];
        }
        return method[target];
    }
}

补充说明:

  • 注:其实不用保存前面所有n个值,只需要保存前两个即可,具体可见10.3

  • 这里是牛客编码链接

Comments


yangzail © 2020. All rights reserved.

Powered by Hydejack v8.5.2