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))
    }

引用声明

该题目引用自
牛客网