矩形覆盖
矩形覆盖
http://www.nowcoder.com/questionTerminal/72a5a919508a4251859fb2cfb987a0e6
描述：
这是一道规律题。
知识点：递归，记忆递归，动态规划，递推
难度:：一星
题解：
方法一：递推
对于这种题没有思路怎么办？
那就对n 从小到大，一步步分析：
n=1时，显然只有一种方法
n=2时，如图有2种方法
n=3，如图有3中方法
n=4,如图有5种方法。
如果到这里，还没有发现规律怎么办呢？
那我们就再分析以下，从n=3到n=4，怎么来的呢？
这里有2种情况：
- 直接在n=3的情况下，再后面中添加一个竖着的。这个很显然成立，有3种情况
- 然后横着的显然能添加到n-2的情况上，也就是在n=2后面，添加2个横着的。有2种情况
所以总结：f [n]表示2*n大矩阵 的方法数。
可以得出：f[n] = f[n-1] + f[n-2]，初始条件f[1] = 1, f[2] =2
所以代码可用递归，记忆递归，和动态规划和递推
这里只写递推代码：
class Solution {
public:
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;
}
};
时间复杂度：O（n）
空间复杂度：O（1）
投递4399游戏等公司7个岗位 >