8.3 矩形覆盖

题目描述

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

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

矩形覆盖 n=3

解题思路

2*n的大矩形,和n个2*1的小矩形

其中 n*2为大矩阵的大小

有以下几种情形:

  1. n <= 0 大矩形为 <= 2*0,直接return 0;
  2. n = 1大矩形为2*1,只有一种摆放方法,return1;
  3. n = 2 大矩形为2*2,有两种摆放方法,return2;
  4. n >2 分为两步考虑:
    • 第一次摆放一块2*1的小矩阵,则摆放方法总共为f(n - 1)
    • 再一次摆放一块2*1的小矩阵,则摆放方法总共为f(n-2);因为,摆放了一块1*2的小矩阵,对应下方的1*2(用××表示)摆放方法就确定了,所以为f(n-2)
  5. 可以看出 f(n) = f(n-1) + f(n-2),就是一个斐波那契数列

代码实现

java 代码

/**
 * 矩形覆盖
 * f(n) = f(n-1) + f(n-2)
 */
public int rectCover(int n) {
    if (n <= 0) {
        return 0;
    } else if (n <= 2) {
        return n;
    } else {
        int a = 1, b = 2, c = 0;
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

public static void main(String[] args){
    System.out.println(rectCover(9));
}

Kotlin 代码

/**
 * 矩形覆盖
 * f(n) = f(n-1) + f(n-2)
 */
private fun rectCover(n: Int): Int {
    return when {
        n <= 0 -> {
            0
        }
        n <= 2 -> {
            n
        }
        else -> {
            var a = 1
            var b = 2
            var c = 0
            for (i in 3..n) {
                c = a + b
                a = b
                b = c
            }
            c
        }
    }
}

/**
 * 入口函数
 */
fun main(args: Array<String>) {
    pringln(rectCover(6))
}

引用声明

该题目引用自
牛客网