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, f(1) = 1

1. 递归,  f(n) = f(n-1) + f(n-2) 很容易想到递归,但是递归过程中存在大量的重复计算,会超时

2. 迭代


class Solution {
public:
int climbStairs(int n) {
assert(n >= 0);
int prevTwo = 0;
int prevOne = 1;
int cur = 1;
for (int i = 1; i <= n; ++i) {
prevOne = cur;
cur = prevOne + prevTwo;
prevTwo = prevOne;
}
return cur;
}
};

3. 直接计算:

斐波那契直接可以计算出表达数出来,且计算方法有好几种:等比数列法、矩阵法、生成函数法

具体见:斐波那契解法


class Solution {
public:
int climbStairs(int n) {
assert(n >= 0);
double s = sqrt(5);
return floor((pow((1+s)/2, n+1) + pow((1-s)/2, n+1)) / s + 0.5);
}
};

时间: 05-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] 509. 斐波那契数

传送门:[LeetCode] 509. 斐波那契数 题目描述 斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列.该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和.也就是: F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N,计算 F(N). 示例 1: 输入:2 输出:1 解释:F(2) = F(1) + F(0) = 1 + 0 = 1. 示例 2: 输入:3 输出:2 解释:F(3) = F

斐波纳契数之组合

斐波纳契数之组合 Time Limit: 1000 MS Memory Limit: 65535 K Total Submit: 145(66 users) Total Accepted: 83(65 users) Rating: Special Judge: No Description 斐波那契数列是这么定义的:F0 = 1, F1 = 1, F2 = F1 + F0,··· Fn = Fn-1 + Fn-2(n>=2),对于每一项,它们都是斐波那契数. 现在给出一个整数d,求一个组合使得a

求斐波那契数的python语言实现---递归和迭代

迭代实现如下: def fab(n): n1 = 1 n2 = 1 if n<1: print("输入有误!") return -1 while (n-2)>0: n3 = n2+n1 n1 = n2 n2 = n3 n-=1 return n3 number = int(input("请输入要求的斐波那契数的第几个数:")) result = fab(number) print(result) 递归实现如下: def fab(n): if n==1 o

Project Euler 104:Pandigital Fibonacci ends 两端为全数字的斐波那契数

Pandigital Fibonacci ends The Fibonacci sequence is defined by the recurrence relation: F[n] = F[n-1] + F[n-2], where F[1] = 1 and F[2] = 1. It turns out that F541, which contains 113 digits, is the first Fibonacci number for which the last nine digi

分治法--二分查找、乘方、斐波那契数

1.二分查找 常见错误: 死循环:循环体外的初始化条件,与循环体内的迭代步骤, 都必须遵守一致的区间规则,也就是说,如果循环体初始化时,是以左闭右开区间为边界的,那么循环体内部的迭代也应该如此.如果两者不一致,会造成程序的错误. 溢出:middle = left + (right - left) / 2 终止条件:一般来说,如果左闭右闭,则left<=right: 如果一开一闭,则left<right: 关键看left能不能等于right,而且要考虑实际情况,有时不能这样简单终结,会出现死循环

UVA 11582 Colossal Fibonacci Numbers! 大斐波那契数

大致题意:输入两个非负整数a,b和正整数n.计算f(a^b)%n.其中f[0]=f[1]=1, f[i+2]=f[i+1]+f[i]. 即计算大斐波那契数再取模. 一开始看到大斐波那契数,就想到了矩阵快速幂,输出等了几秒钟才输出完,肯定会超时.因为所有计算都是要取模的,设F[i]=f[i] mod n.F[0]=F[1]=1.只要出现F[i]=F[i+1]=1,那么整个序列就会重复.例如n=3,则序列为1,1,2,0,2,2,1,0,1,1……第九项和第十项都等于1,所以之后的序列都会重复. 至

算法笔记_001:斐波那契数的多种解法

本篇文章解决的问题来源于算法设计与分析课程的课堂作业,主要是运用多种方法来计算斐波那契数.具体问题及解法如下: 一.问题1: 问题描述:利用迭代算法寻找不超过编程环境能够支持的最大整数的斐波那契数是第几个斐波那契数.(Java: 231-1 for int, 263-1 for long) 解决方案:针对问题1,此处要使用迭代法来解决,具体实现代码如下: //用迭代法寻找编程环境支持的最大整数(int型)的斐波那契数是第几个斐波那契数 public static int max_int_iter

组合数学及其应用——斐波那契数

斐波那契数列是一个非常有名的数列,它有着各种各样神奇的性质并且和自然界有着千丝万缕的联系.通过这篇文章我们将详细的阐述这个看似简单的数列的背后蕴含的神奇性质. 引入斐波那契数的问题: 在一年的开始,把新生的雌雄一对兔子放进一个笼子里.从第二个月开始,每个月这个雌兔子胜出雌雄一对兔子.而每对新出生的雌雄兔子也从第二个月开始生兔子,确定一年后笼子里有多少对兔子? 分析:我们直接考虑通过递推的方法来得到这个问题的泛解(即任意个月后的数量都可以计算),我们记f[n]表示第n天的兔子数量,它的来源有两个: