点击量：748
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?
思路：这个题目第一反应是用递归去计算，于是有了下面的代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class Solution { public static int count = 0; public int climbStairs(int n) { func(0, n); return count; } //func(0,n) public void func(int x, int n){ if(x == n){ count++; }else if(x < n){ func(x+1, n); func(x+2, n); } return; } } |
这样的思路最简单，但是仔细看看就会发现，递归里有很多重复计算，而且当n很大时，这种方法的函数堆栈压的太深，栈溢出导致效率很低。
那么就得换一种思路了，其实到达第n级楼梯的步数（f(n)）就等于前一级楼梯的步数f(n – 1) 和前二级楼梯的步数f(n -2)之和。为什么呢？因为每次只能走一步或者两步！因此，代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class Solution { //'cause it only climbs 1 or 2 steps one time，so distinct ways of step n is the sum of ( n -1 ) and (n - 2) public int climbStairs(int n) { if(n <= 0){ return 0; } if(n <= 2){ return n; } int sum = 0; int pre = 1; int cur = 2; for(int i=2; i<n; i++){ sum = pre + cur; pre = cur; cur = sum; } return sum; } } |
这种方式没有递归，非常快。
