爬樓梯問題

題目：

          假設你正在爬樓梯。需要 n 階你才能到達樓頂。每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？

          注意：給定 n 是一個正整數。

解析：

假如要爬上第i階（i>=2)，則有兩種方式：

    1、從第i-1階跳一步到第i階

    2、從第i-2階跳兩步到第i階

記f(i)為爬上第i階的方法數量，則

第一種方法（遞歸）：

從公式上看，這是一個遞歸方程，是以首先想到的應該是采用遞歸的方法解決，其代碼也非常簡潔：

為了考慮資料的溢出，是以這裡采用了long long int，到時候改回int就行了。

要正确的設定遞歸基 。衆所周知，遞歸算法的一個缺陷是存在大量重複的計算，其時間複雜度為

。我的機器上到n取40左右就明顯速度很慢了。

#include <iostream>
#include <vector>
long long int clumbStairs(int n);
int main()
{
	int n;
	std::cout << "請輸入階梯數：";
	while (std::cin >> n && n >= 0) {
		std::cout << "共有：" << clumbStairs(n) << "種走法" << std::endl;
		std::cout << "請輸入階梯數：";
	}
	system("pause");
	return 0;
}

//這種方法時間複雜度太高
long long int clumbStairs(int n)
{
	if (n == 1)
		return 1;
	if (n == 2)
		return 2;

	return clumbStairs(n - 1) + clumbStairs(n - 2);
} 
           

第二種方法（動态規劃）：

   由遞推方程

可以看出，

的結果依賴于子問題

和

的結果，是以不難寫出如下的代碼。

#include <iostream>
#include <vector>
long long int clumbStairs(int n);
int main()
{
	int n;
	std::cout << "請輸入階梯數：";
	while (std::cin >> n && n >= 0) {
		std::cout << "共有：" << clumbStairs(n) << "種走法" << std::endl;
		std::cout << "請輸入階梯數：";
	}
	system("pause");
	return 0;
}

long long int clumbStairs(int n) {
   long long int Count = 0;
	if (n > 0) {
		if (1 == n)
			Count = 1;
		else if (2 == n)
			Count = 2;
		else {
			long long int* dp = new long long int[n + 1];
			dp[0] = 0, dp[1] = 1, dp[2] = 2;
			for (int i = 3; i <= n; ++i)
				dp[i] = dp[i - 1] + dp[i - 2];

			Count = dp[n];
			delete [] dp;
		}
	}
	return Count;
}