一道简单分治题
题目描述
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
先模拟一下
n = 1 ---- res = 1
n = 2 ---- res = 2
n = 3 ---- res = 3
n = 4 ---- res = 5
...
可以看出 res(n) = res(n-1) + res(n-2), 又是斐波那契的应用。
递归解决(n太大函数栈可能会溢出)
class Solution { public: int rectCover(int number) { if(number <= 0) return number; if(number == 1) return 1; if(number == 2) return 2; return rectCover(number-1)+rectCover(number-2); } };
动态规划
1 class Solution { 2 public: 3 int rectCover(int number) { 4 if(number <= 0) 5 return number; 6 7 int r1 = 1; 8 int r2 = 2; 9 int res; 10 for(int i=3; i<=number; i++) 11 { 12 res = r2+r1; 13 r1 = r2; 14 r2 = res; 15 } 16 return res; 17 } 18 };