Leetcode: Climbing Stairs

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?

这道题目是求跑楼梯的可行解法数量。每一步可以爬一格或者两个楼梯，可以发现，递推式是f(n)=f(n-1)+f(n-2)，也就是等于前一格的可行数量加上前两格的可行数量。熟悉的朋友可能发现了，这个递归式正是斐波那契数列的定义. 这里base case 是f(1)=1, f(2)=2. Fibonacci是典型的动态规划问题，用Recursion和Iteration都可以，下面列举了Code Ganker写的Iterative解法：

 1 public int climbStairs(int n) {
 2     int f1 = 1;
 3     int f2 = 2;
 4     if(n==1)
 5         return f1;
 6     if(n==2)
 7         return f2;
 8     for(int i=3;i<=n;i++)
 9     {
10         int f3 = f1+f2;
11         f1 = f2;
12         f2 = f3;
13     }
14     return f2;
15 }

用Recursion要小心，比如这种：

 1 public class Solution {
 2     public int climbStairs(int n) {
 3         if (n<=0)
 4         return 0;
 5         if (n==1)
 6         return 1;
 7         if (n==2)
 8         return 2;
 9         return climbStairs(n-1)+climbStairs(n-2);
10     }
11 }

这个递归是指数量级的，n大了会超时～你递归还是应该用动态规划来实现～也就是要保存历史信息，然后传下去哈～