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阶,你有两种爬法,每次爬一阶或者两阶。请问你有多少种爬法到达楼梯顶部。

  1. public int ClimbStairs(int n) {
  2. if(n == 0)
  3. return 0;
  4. int pre = 0;
  5. int cur = 1;
  6. int tempCur = 0;
  7. for (int i = 1; i <= n; i++)
  8. {
  9. tempCur = cur;
  10. cur = pre + cur;
  11. pre = tempCur;
  12. }
  13. return cur;
  14. }

求斐波那契数列

  1. static public int[] Fibonacci(int n)
  2. {
  3. int[] arr = new int[n+1];
  4. arr[0] = 0;
  5. arr[1] = 1;
  6. for (int i = 2; i < n + 1; i++)
  7. {
  8. arr[i] = arr[i - 1] + arr[i - 2];
  9. }
  10. return arr;
  11. }

来自为知笔记(Wiz)

时间: 01-12

70. 爬梯子问题(斐波那契数列)Climbing Stairs的相关文章

js算法集合(二) javascript实现斐波那契数列 (兔子数列) Javascript实现杨辉三角

js算法集合(二)  斐波那契数列.杨辉三角 ★ 上一次我跟大家分享一下做水仙花数的算法的思路,并对其扩展到自幂数的算法,这次,我们来对斐波那契数列和杨辉三角进行研究,来加深对Javascript的理解. 一.Javascript实现斐波那契数列 ①要用Javascript实现斐波那契数列,我们首先要了解什么是斐波那契数列:斐波那契数列(Fibonacci sequence),又称黄金分割数列.因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为

快速求斐波那契数列(矩阵乘法+快速幂)

斐波那契数列 给你一个n:f(n)=f(n-1)+f(n-2) 请求出 f(f(n)),由于结果很大请 对答案 mod 10^9+7; 1<=n<=10^100; 用矩阵乘法+快速幂求斐波那契数列是经典应用: 矩阵公式 C i j=C i k *C k j; 根据递推式 构造2*2矩阵: 原始矩阵 1 0 0 1 矩阵 2 1 1 1 0 原始矩阵与矩阵 2相乘达到转化状态效果: 对矩阵二进行快速幂 乘法:达到快速转化矩阵的效果: 即使达到快速转化状态:那么大的数据范围也很难求解: 高精?这有

bzoj 3657 斐波那契数列(fib.cpp/pas/c/in/out)

空间 512M  时限2s [题目描述] 有n个大于1的正整数a1,a2,…,an,我们知道斐波那契数列的递推式是f(i)=f(i-1)+f(i-2),现在我们修改这个递推式变为f(i)=f(i-1)+f(i-2)+r(i-1),其中r(x)为a1,a2,…,an中为x的约数的个数.现在要求f(m) mod 19940417的值.注:初值f(1)=1,f(2)=1 输入格式: 第一行两个数n,m. 接下来一行n个正整数a1,a2,…,an. 输出格式: 输出一行仅一个数,f(m) mod 199

斐波纳契数列

查找斐波纳契数列中第 N 个数. 所谓的斐波纳契数列是指: 前2个数是 0 和 1 . 第 i 个数是第 i-1 个数和第i-2 个数的和. 斐波纳契数列的前10个数字是: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ... 样例 给定 1,返回 0 给定 2,返回 1 给定 10,返回 34 虽然这道题是一道入门级的题目,可是在第一遍做的时候并没有多想,直接使用的递归,然后数据通过95%,显示的到47的时候就溢出了.经过学习前辈的经验,该题的收获如下: 方法1:使用递归解,

hdu 4549 M斐波那契数列(快速幂 矩阵快速幂 费马小定理)

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=4549: 题目是中文的很容易理解吧.可一开始我把题目看错了,这毛病哈哈. 一开始我看错题时,就用了一个快速幂来解,不用说肯定wa,看题目的通过率也不高,我想会不会有啥坑啊.然而我就是那大坑,哈哈. 不说了,直接说题吧,先讨论k=1,2,3;时的解.这应该会解吧,不多说了: 从第四项开始f(4)=a^1+b^2;f(5)=a^2+b^3;f(6)=a^3+b^5......; 看出来了吧,a上的指数成斐波

剑指OFFER之斐波那契数列

题目描述: 大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项.斐波那契数列的定义如下: 输入: 输入可能包含多个测试样例,对于每个测试案例, 输入包括一个整数n(1<=n<=70). 输出: 对应每个测试案例, 输出第n项斐波那契数列的值. 样例输入: 3 样例输出: 2 注意:这道题目用递归的话会做大量的重复计算,效率很低.Code: #include <iostream> using namespace std; long long Fibonacc

最优化算法-斐波那契数列搜索

斐波那契数列搜索,参考Edwin<最优化导论>第四版7.3章节,算法采用go语言实现. /***************************************** * FileName : fibonacci_search.go * Author : fredric * Date : 2017.09.01 * Note : 斐波那契数列搜索算法 * History : *****************************************/ package search

【Java】斐波那契数列(Fibonacci Sequence、兔子数列)的3种计算方法(递归实现、递归值缓存实现、循环实现)

斐波那契数列:0.1.1.2.3.5.8.13………… 他的规律是,第一项是0,第二项是1,第三项开始(含第三项)等于前两项之和. > 递归实现 看到这个规则,第一个想起当然是递归算法去实现了,于是写了以下一段: public class RecursionForFibonacciSequence { public static void main(String[] args) { System.out.println(recursion(10)); } public static double

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 阶楼梯的方法数,为