剑指offer:矩形覆盖 冷不防 2021-06-24 16:00 403阅读 0赞 **试题:** 我们可以用2\*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\*1的小矩形无重叠地覆盖一个2\*n的大矩形,总共有多少种方法? **代码:** 同样是总结出规律,然后使用迭代,当n=1时,只有一种方法;当n=2时,只有两种方法;当n=3时,只有三种方法。从n=3往回推,假设所有矩形已经填满,这是时减去一个矩形就得到n-1的情况;减去两个矩形就是n-2的情形;当减去3个的矩形时就会发现,从n-3情况下无论如何填充,其下一步都是n-1或者n-2情况。也就是说n-3的情形已经被包含在n-1或n-2当中了。 class Solution { public: int rectCover(int number) { if(number==0) return 0; int first = 1; int second = 2; while(number-->1){ second = first + second; first = second - first; } return first; } };
还没有评论,来说两句吧...