在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
题目:我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法? 分析:实际上还是一道斐波那契数列的应用,要填2*n的大矩形,我们可以先在大矩形左侧竖着放置一个2*1的小矩形,此时右边还剩下2*(n-1)的区域,如果横着置于左上角需要两个2*1的小矩形,右边还剩下2*(n-2)的区域,那么方法数f(n) = f(n-1) + f(n-2)。 程序:C++ class Solution { public: int rectCover(int number) { if(number == 0) return 0; if(number == 1) return 1; if(number == 2) return 2; int fNum = 1; int sNum = 2; int temp = 0; for(int i = 3; i <= number; ++i){ temp = sNum; sNum = fNum + sNum; fNum = temp; } return sNum; } }; Java public class Solution { public int RectCover(int target) { if(target == 0) return 0; if(target == 1) return 1; if(target == 2) return 2; int fNum = 1; int sNum = 2; int temp = 0; for(int i = 3; i <= target; ++i){ temp = sNum; sNum = fNum + sNum; fNum = temp; } return sNum; } }
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论