首页 > 代码库 > leetcode 刷题之路 92 Climbing Stairs
leetcode 刷题之路 92 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?
一个台阶总共有n级,如果一次可以跳1级,也可以跳2级,求总共有多少总跳法。
分析:
一次最多只能跳两级,那么对于第n级(n>=2)台阶,显然只能从第n-1级跳一级到达或者从第n-2级跳两级到达,因此只要知道了n-1级和n-2级的跳法个数,求和就是第n级的跳法个数。
设跳法个数为f(n),n为台阶级数,则有:
f(n)=f(n-1)+f(n-2),
当n=0,1时,f(n)=1
题目转换成一个典型的Fibonacci序列问题。
Accepted Solution:
class Solution { public: int climbStairs(int n) { int first=1,second=1; for(int i=2;i<=n;i++) { int temp=second; second=first+second; first=temp; } return second; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。