频道栏目
首页 > 考试 > 其他 > 正文

Climbing Stairs 爬楼梯问题解析

2018-06-28 14:08:47         来源:zhangzhetaojj的博客  
收藏   我要投稿

题目:

假设你正在爬楼梯。需要?n?步你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定?n?是一个正整数。

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1.  1 步 + 1 步
2.  2 步

示例 2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1.  1 步 + 1 步 + 1 步
2.  1 步 + 2 步
3.  2 步 + 1 步

解题思路:

这是一个斐波那契数列问题,假设只有一级台阶,那就只有一种走法那就是走一步;假如由两级台阶,那就有两种走法,可以走两个一级和一个两级;那如果有三级台阶呢?

走三级台阶的方法就是对只有一级台阶的所有情况再走两级或者是只有两级台阶的左右情况再走一级,可以推导出:

F(3) = F(2) + F(1);进一步:

F(N) = F(N - 1) + F(N - 2),那代码实现起来就很简单了。

代码实现:

class Solution {
 public int climbStairs(int n) {
  int a = 1, b = 2;
  if (n == 1) return a;
  if (n == 2) return b;
  for (int i = 2; i < n; i ++) {
int tmp = b;
b = a + b;
a = tmp;
  }
  return b;
 }
}
上一篇:Find the Duplicate Number(二分和List)
下一篇:用两种方法求解九宫算问题
相关文章
图文推荐
热门新闻

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站