【题目描述】
我们可以用2×1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2×1的小矩形无重叠地覆盖一个2×n的大矩形,总共有多少种方法?
eg:
比如n=3时,23的矩形块有3种覆盖方法:
【解法】
n=1
n=2
n=3
n=4
如果到这里,还没有发现规律怎么办呢?
那我们就再分析以下,从n=3到n=4,怎么来的呢?
这里有2种情况:
直接在n=3的情况下,再后面中添加一个竖着的。这个很显然成立,有3种情况
然后横着的显然能添加到n-2的情况上,也就是在n=2后面,添加2个横着的。有2种情况
通过以上分析,发现刚好和图中的个数一样。
所以总结:f [n]表示2n大矩阵 的方法数。
可以得出:f[n] = f[n-1] + f[n-2],初始条件f[1] = 1, f[2] =2
所以代码可用递归,记忆递归,和动态规划和递推
这里只写递推代码:
int rectCover(int n) {
if (n==0 || n==1 || n==2) return n;
int a = 1, b = 2, c;
for (int i=3; i<=n; ++i) {
c = a + b;
a = b;
b = c;
}
return c;
}
**总结:**JZ7、8、9、10都是一类题。