https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6
第一次做是真的没思路……

递归

首先如果n=0,则只有0种;
如果n=1,也只有1种;
如果n=2,有横竖2种情况:
矩阵覆盖 - 图1
如果n=3,有3种情况:
矩阵覆盖 - 图2
而如果n=4,有5种情况:
矩阵覆盖 - 图3
由规律发现,2∗n 的矩形的情况数为f(n)=f(n−1)+f(n−2),即这就是一个斐波那契数列,按照斐波那契数列的解法来即可,需要注意不同点在于n小于等于2时,都只有n种。

  1. public static int rectCover(int target) {
  2. if (target <= 2)
  3. return target;
  4. return rectCover(target - 1) + rectCover(target - 2);
  5. }