Climbing Stairs

点击量:460

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很大时,这种方法的函数堆栈压的太深,栈溢出导致效率很低。
那么就得换一种思路了,其实到达第n级楼梯的步数(f(n))就等于前一级楼梯的步数f(n – 1) 和前二级楼梯的步数f(n -2)之和。为什么呢?因为每次只能走一步或者两步!因此,代码如下:

这种方式没有递归,非常快。

发表评论

电子邮件地址不会被公开。 必填项已用*标注