本题的本质是斐波那契数列 设:长度为n时,覆盖方法为f(n);当n=1的时候,f(1) = 1,当n=2的时候,f(2) = 2。当n>2的时候,长方形覆盖可以拆解成更小的集合操作。 比如最后填充的是一个21的区域,那么只需要计算f(n-1)的覆盖方法数,就是最后填充21区域的方法数; 如果最后填充的是一个22的区域,只需要计算f(n-2)的覆盖方法数,即为最后填充22区域的方法数; 但是我们会发现最后填充22的区域时,有一种填法与21区域重合,所以此时这种放置方式所有的方法都是情况1(最后填充21)的子集,需要去掉该覆盖情况所有的方法数,此时f(n) = f(1)f(n-1) + (...