剑指offer - 矩阵覆盖 - JavaScript

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

题目描述

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

专注前端与算法的系列干货分享,欢迎关注(¬‿¬):
「微信公众号:心谭博客」| xxoo521.com | GitHub

解法 1: 斐波那契数列

这题和“青蛙跳台阶”类似,也是斐波那契数列的变形。

假设覆盖2*n矩形有 f(n) 种方法。那么这个2*n的矩形可能由2*(n-1)2*(n-2)的矩形直接一步变化而来。如下图所示:

因此 f(n) = f(n - 1) + f(n - 2)

代码如下:

// 原文地址:https://xxoo521.com/2019-12-30-ju-zhen-fu-gai/
// ac地址:https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6

/**
 * @param {number} number
 * @return {number}
 */
function rectCover(number) {
    if (number === 0) {
        return 0;
    }

    const cache = {
        0: 0,
        1: 1
    };
    return __rectCover(number + 1);

    function __rectCover(n) {
        if (cache[n] !== undefined) {
            return cache[n];
        }

        cache[n] = __rectCover(n - 1) + __rectCover(n - 2);
        return cache[n];
    }
}

斐波那契相关题目

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×