一、题目：斐波那契算法

给定整数N，返回斐波那契数列的第N项。

递归代码：时间*O（2**N）

def Fal(N):    if N <= 0:        return 0    if N <= 2:        return 1    return Fal(N-1) + Fal(N-2)

非递归代码：动态规划：时间O（N)，一个一个加和

def Fal(N):    if N <= 0:        return 0    if N <= 2:        return 1    stack = [1,1]    for i in range(3,N+1):        stack.append(stack[-1]+stack[-2])    return stack[-1]

非递归代码：时间O（logN)，求一个矩阵N次方的值。

斐波那契可转化成矩阵N次方的问题。

 

---

二、题目：爬楼梯：动态规划：时间O（N)

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2输出： 2解释： 有两种方法可以爬到楼顶。1.  1 阶 + 1 阶2.  2 阶

示例 2：

输入： 3输出： 3解释： 有三种方法可以爬到楼顶。1.  1 阶 + 1 阶 + 1 阶2.  1 阶 + 2 阶3.  2 阶 + 1 阶

 

 思路：斐波那契，f(1) = 1,f(2)=2，f(n) = f(n-1)+f(n-2)。

 

---

三、矩形覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

思路：

既然是长条形的，那么从后向前，最后一个矩形2*2的，只有两种情况：      

第一种是最后是由一个2*(n-1)的矩形加上一个竖着的2*1的矩形　　

另一种是由一个2*(n-2)的矩形，加上两个横着的2*1的矩形　　

因此我们可以得出，　　

第2*n个矩形的覆盖方法等于第2*(n-1)加上第2*(n-2)的方法。

代码：

def rectCover(self, number):        # write code here        if number == 0:            return 0        elif number <= 2:            return number        dp = [0] * (number+1)        dp[1] , dp[2] = 1 , 2        for i in range(3,number+1):            dp[i] = dp[i-2] + dp[i-1]        return dp[-1]