Tag name:Recursion

[LeetCode] Climbing Stairs (Fibonacci Sequence)

01/23/2014 / 2 Comments

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

假设N级阶梯有F(N)种走法,每种走法的最后一步是1步或者2步,那么F(N)可以看成是先走F(N-1)种走法,然后再走最后一步,以及先走F(N-2)种走法,然后再走最后两步,于是F(N)=F(N-1)+F(N-2),实际上就是另外一个斐波那契数列,只不过F(1)=1,F(2)=2

问题其实很简单就能想通了,关键是如何实现最佳,经典的递归实现如下:

这个实现似乎是最糟糕的一种,时间复杂度中n在指数位置。(以上代码放到LeetCode上绝对是Runtime Err)他的坑爹之处就在于,对于同一个输入N,递归调用了好多次。例如要计算F(5),由于F(5)=F(4)+F(3),于是开始先算F(4)了,在算F(4)的过程中,F(3)肯定是被算过了,但实际上我们在F(4)的调用栈跑完之后,又还要去跑一遍F(3)

改进之后的想法是建一个数组把之前的结果都存起来,这样就可以回头lookup而不用再算了:

这个做法时间复杂度O(n),但空间复杂度似乎还不是最优,实际上在算完F(k)之后,F(k-2)就再也用不到了,让他出队就行了,这里就不用队列了,只有两个元素,迭代一下就OK:

最后,还可以直接用通项公式来做,不过由于double的精度问题,比较大的输入可能会有误差,推导过程我Google了一下,似乎感觉高中学过,对第一步构造等比数列有印象

不知道math里面的pow是怎么实现的,如果是乘法实现的话那时间复杂度也得是N在指数位置的级别,所以面试要真遇上这题,我决定就说一下知道有通项公式,就不这么写代码了。