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?

原题链接：https://oj.leetcode.com/problems/climbing-stairs/

题目：你在爬楼梯。

须要 n 步才干到顶部。

每次你爬1 或 2 步。

有多少种独立的爬到顶部的方式？

思路：首先非常easy就想到了递归的解法。可是超时了。

public int climbStairs(int n) {		if(n < 0)			return 0;		if(n <= 1)			return 1;		return climbStairs(n - 1) + climbStairs(n - 2);	}

所以採用非递归的方式。事实上此题类似于求斐波那契数列的和，可是递归不仅慢还可能溢出。以下採用非递归的方法，当中pre代表前n-1台阶的方法数，current代表第n台阶的方法数。

public int climbStairs(int n) {		if (n == 0 || n == 1)			return 1;		int pre = 1;		int current = 1;		for (int i = 2; i <= n; i++) {			int temp = current + pre;			pre = current;			current = temp;		}		return current;	}