Leetcode: Climbing Stairs
Leetcode: Climbing Stairs
卡尔曼和玻尔兹曼谁曼
发布于 2019-01-22 17:32:10
发布于 2019-01-22 17:32:10
题目： 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) 表示爬 n 阶楼梯的不同方法数，为了爬到第 n 阶楼梯，有两个选择：一是 从第 n - 1 阶前进 1 步；二是从第 n - 2 阶前进 2 步；因此，有 f (n) = f (n 1) + f (n 2)。这是一个斐波那契数列。 当n=1时结果为1，当n=2时结果为2。
代码一：
int climbStairs(int n)
{
if (n < 0)
{
return -1;
}
if (n <= 2)
{
return n;
}
else
{
return climbStairs(n - 1) + climbStairs(n - 2);
}
}这个提交以后提示超时了！
代码二：
int climbStairs(int n)
{
if (n < 0)
{
return -1;
}
if (n <= 2)
{
return n;
}
else
{
int *step = new int[n];
step[0] = 0;
step[1] = 1;
for (int i = 2; i < n; i++)
{
step[i] = step[i - 1] + step[i - 2];
}
int result = step[n - 1];
delete []step;
return result;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年03月13日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读