leetcode笔记: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阶楼梯共有几种爬法-_-||。题目可以看成是,设f(n)表示爬到第n 阶楼梯的方法数,为了爬到第n阶楼梯,有以下两种选择:

? 从第f(n-1)阶前进1步;

? 从第f(n-2)阶前进2步;

f(n)可写成:f(n) = f(n-1) + f(n-2)

题目转化为斐波那契数列的问题,关于这一内容,网上相关研究有很多,概念传送门:

http://baike.baidu.com/link?url=c2Bmk2jBGbI46qTIA-qKmdTkYBrVYYrejAHzf8BJRwCekIL4Sbx48fFCRkeGdul0

二.题目分析

关于斐波那契序列,可以使用递归或者迭代来解决问题,该书列可写成以下递推关系:

显然,使用递推关系式反复迭代并不是最优的解法,在计算f(n)值时,需要计算f(1),f(2),…,f(n-1)的所有值,其中存在很多重复的运算,如计算f(4)=f(3)+f(2),其中需要求解f(3)=f(2)+f(1)。若使用一个数组用于储存所有计算过的项,可以把时间复杂度降至O(n),而空间复杂度也为O(n)。

这里为了追求时间复杂度,因此直接使用斐波那契的通项公式,该公式的推导过程如下:

三.示例代码

#include <iostream>
using namespace std;

class Solution
{
public:
    // 时间复杂度O(1)
    int climbStairs1(const int n)
    {
        const double sqrtNum = sqrt(5);
        return int(floor((pow((1 + sqrtNum) / 2, n + 1) - pow((1 - sqrtNum) / 2, n + 1)) / sqrtNum));
    }

    // 时间复杂度O(n)
    int climbStairs2(const int n)
    {
        int current = 1;
        int last = 0;
        for (int i = 1; i <= n; i++)
        {
            int temp = current;
            current += last;
            last = temp;
        }
        return current;
    }
};

简单的测试代码:

#include "ClimbingStairs.h"
#include <iostream>

int main()
{
    int n;
    cout << "How many stairs? " << "Input: ";
    cin >> n;
    Solution s;
    int result1 = s.climbStairs1(n);
    int result2 = s.climbStairs2(n);

    cout << "How many ways to reach the finish line? " "Result1:" << result1 << endl;
    cout << "How many ways to reach the finish line? " "Result2:" << result2 << endl;
    system("pause");
    return 0;
}

四.小结

其实使用通项公式也存在漏洞,因为通项公式使用浮点运算,还出现了物理书,因此不能保证结果的精度。而在《编程之美》一书中,还给出一种分治策略的解决方法。该算法可做到时间复杂度O(Log2n),而网上更有博文写出了七种解斐波那契序列的方法,还要继续深入研究啊。

版权声明:本文为博主原创文章,未经博主允许不得转载。

时间: 09-13

leetcode笔记:Climbing Stairs(斐波那契数列问题)的相关文章

[LeetCode] 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? Show Tags 这题其实就是斐波那契数列来的. #include <iostream> using namespace std; class Solution {

LeetCode | 面试题10- I. 斐波那契数列【剑指Offer】【Python】

LeetCode 面试题10- I. 斐波那契数列[剑指Offer][Easy][Python][动态规划] 问题 力扣 写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项.斐波那契数列的定义如下: F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出. 答案需要取模 1e9+7(1000000007),如计算初始结果为:10000000

Leetcode: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层有f(n)中走法,因为每次只能走1步或2步,则 f(n) = f(n-1) + f(n-2) 很明显是一个斐波那契数,f(0) = 0,

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? 假设你在爬一个楼梯,该楼梯有n阶,你有两种爬法,每次爬一阶或者两阶.请问你有多少种爬法到达楼梯顶部. public int ClimbStairs(int n) { i

13、蛤蟆的数据结构笔记之十三栈的应用之栈与递归之斐波那契数列

13.蛤蟆的数据结构笔记之十三栈的应用之栈与递归之斐波那契数列 本篇名言:"人生不是一支短短的蜡烛,而是一支由我们暂时拿着的火炬,我们一定要把它燃得." 继续递归的斐波那契数列问题. 欢迎转载,转载请标明出处: 1.  斐波那契数列 斐波那契数列,又称黄金分割数列,指的是这样一个数列:0.1.1.2.3.5.8.13.21.--在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)在现代物理.准晶体结构.化学

Python初学者笔记:打印出斐波那契数列的前10项

问题:斐波那契数列(意大利语: Successione di Fibonacci),又称黄金分割数列.费波那西数列.费波拿契数.费氏数列,指的是这样一个数列:0.1.1.2.3.5.8.13.21.--在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*),用文字来说,就是斐波那契数列列由 0 和 1 开始,之后的斐波那契数列系数就由之前的两数相加.特别指出:0不是第一项,而是第零项. 方法:Python2.7.9 a=0 b=

斐波那契数列实例讲解以及C++实现

斐波那契数列,又称黄金分割数列,指的是这样一个数列:0.1.1.2.3.5.8.13.21.--在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)在现代物理.准晶体结构.化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963起出版了以<斐波纳契数列季刊>为名的一份数学杂志,用于专门刊载这方面的研究成果. 斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,

对斐波那契数列的理解

在数学上,费波那契数列是以递归的方法来定义: (n≧2) 费波那契数列由0和1开始,之后的费波那契系数就是由之前的两数相加而得出. 与斐波那契数列有关的问题,都符合这样的描述: 当前状态的得出是依赖于前两项的状态,给出初始状态F(0),F(1),之后的每一项都满足共同的特点,即为前两项状态相加. 前两项的状态,分别为当前状态的两种解法,适用加法原理. 下面给出几个例题: 1.Climbing Stairs 爬楼梯问题 每次只能爬1或2步,那么爬到第n层的方法要么是从第n-1层一步上来的,要不就是

#斐波那契数列用矩阵快速幂求解f(n)#

通常情况下,斐波那契数列第n项可以通过递归求解或者直接求解但当n非常大的时候,求解f(n)将显得非常困难下面利用矩阵以及快速幂的方法在logn复杂度内求解 则可以运用快速幂来求解矩阵高次幂,复杂度降为logn 来自为知笔记(Wiz)