刷题70. Climbing Stairs

一、题目说明

题目70. Climbing Stairs，爬台阶（楼梯），一次可以爬1、2个台阶，n层的台阶有几种爬法。难度是Easy！

二、我的解答

类似的题目做过，问题就变得非常简单。首先用递归方法计算：

class Solution{

	public:

		int climbStairs(int n){

			if(n==1) return 1;

			if(n==2) return 2;

			return climbStairs(n-1) + climbStairs(n-2);

		}

};

非常不好意思，Time Limit Exceeded。

那就用dp算法吧：

class Solution{

	public:

		int climbStairs(int n){

			if(n==1) return 1;

			if(n==2) return 2;

			vector<int>dp;

			dp.push_back(1);

			dp.push_back(2);

			for(int i=2;i<n;i++){

				dp.push_back(dp[i-1]+dp[i-2]);

			}

			return dp[n-1];

		}

};

性能：

Runtime: 4 ms, faster than 55.03% of C++ online submissions for Climbing Stairs.

Memory Usage: 8.4 MB, less than 51.47% of C++ online submissions for Climbing Stairs.

三、优化措施

不优化了！

巴特西

刷题70. Climbing Stairs

最新文章

热门文章