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>=3时,f(n)=f(n-1)+f(n-2)。

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>=3时,f(n)=f(n-1)+f(n-2)。

C++代码实现:

#include<iostream>
using namespace std;

class Solution {
public:
    int climbStairs(int n) {
        if(n==0)
            return 0;
        if(n==1)
            return 1;
        if(n==2)
            return 2;
        int n1=1;
        int n2=2;
        int sum=0;
        while(n>2)
        {
            sum=n1+n2;
            n1=n2;
            n2=sum;
            n--;
        }
        return sum;
    }
};

int main()
{
    int n=5;
    Solution s;
    cout<<s.climbStairs(n)<<endl;
}

运行结果:

相关文章
|
6月前
|
算法
hdoj 4712 Hamming Distance(靠人品过的)
在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的字符不同的个数。换句话说,它就是将 一个字符串变换成另外一个字符串所需要替换的字符个数。
20 0
LeetCode 70. Climbing Stairs
你正在爬楼梯。 它需要n步才能达到顶峰。 每次你可以爬1或2步。 您可以通过多少不同的方式登顶? 注意:给定n将是一个正整数。
40 0
LeetCode 70. Climbing Stairs
LeetCode 70. 爬楼梯 Climbing Stairs
LeetCode 70. 爬楼梯 Climbing Stairs
Leetcode-Easy 70. Climbing Stairs
Leetcode-Easy 70. Climbing Stairs
79 0
Leetcode-Easy 70. Climbing Stairs
HDU-1027,Ignatius and the Princess II
HDU-1027,Ignatius and the Princess II
|
人工智能
HDOJ 1028 Ignatius and the Princess III(递推)
HDOJ 1028 Ignatius and the Princess III(递推)
98 0
|
算法 移动开发
[LeetCode]--70. 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? 这是一个很经典的爬楼梯问题,面试也会经常遇
1128 0