Climbing Stairs

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?

思路：

（1）題意為有一個n階的梯子，一次你只能上一個或兩個台階，求你有多少種上台階的方法。這道題其實很簡單，就看你能不能想到它和某一個挺有名數列之間的聯系，其考察我們發現規律和對常見數學數列理解的能力。

（2）這裡我們不妨列舉，並從中發現規律：

當n=1時，ways=1

當n=2時，有[2] [1,1]兩種情況，ways=2

當n=3時，有[1,1,1] [1,2] [2,1]三種情況，ways=3

當n=4時，有[1,1,1,1] [2,2] [1,1,2] [1,2,1] [2,1,1]五種情況，ways=5

當n=5時，有[1,1,1,1,1] [2,2,1] [2,1,2] [1,2,2] [1,1,1,2] [1,1,2,1] [1,2,1,1] [2,1,1,1]八種情況，ways=8

（3）這樣我想你一眼就能看出規律了，當n>3時，n對應的情況數字為n-1和n-2之和。此時，規律正好和斐波那契數列出現的規律對應。

（4）斐波拉切數列是這樣一個數列：1、1、2、3、5、8、13、21、……在數學上，其被以遞歸的方法定義：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2）

（5）這樣，我們就能夠用遞歸的方法求得結果了。其實，很多題目看似挺難的樣子，可能一時半刻想不到好的解題思路，就像這道題一樣，剛開始我也沒啥頭緒，後來我就嘗試先列舉一排數字看看結果，然後就發現這不正好和斐波拉切數列對應的麼，知道斐波拉切數列，結果也就出來了。所以我建議大家遇到看似挺難的題時，要去分析題目，一步步去理解，可能答案在你分析的過程中就會浮現出來，不要放棄。

（6）注：斐波拉切數列的另一種常見表述為“生兔子問題”。之前遇到的好多校招筆試題中都會出現這個題目，所以找工作同學可以多關注一下這個數列。其算法實現用遞歸很容易實現。希望對你有所幫助。謝謝。

算法代碼實現如下所示：

public int climbStairs(int num) {
	//該題目和斐波拉切數列、生兔子問題屬於同一類問題
	// 如果定義為 int則num=46時會越界；如果定義為long則num=92時會越界
	if (num <= 0)
		return 0;
	int[] sum = new int[num+1];
	for (int i = 0; i <= num; i++) {
		if (i == 0)
			sum[i] = 1;
		if (i == 1)
			sum[i] = 1;
		if (i > 1) {
			sum[i] = sum[i - 1] + sum[i - 2];
		}
	}
	return sum[num];
}