剑指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];
  }
}

# 斐波那契相关题目