问题
- 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N – 1) + F(N – 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
解决
// 1、递归,使用了hash进行存储值，减少了重复计算的消耗
class Solution {
private static int MOD=1000000007; //取模
private HashMap map=new HashMap();
public int fib(int n) {
if(n
//2、动态规划
class Solution{
private static int MOD=1000000007;
public int fib(int n){
if(n
总结
- 两种算法都是时间复杂度O(n)
- 第一种空间复杂度O(n),第二种O(1)
Original: https://www.cnblogs.com/zhangsanM/p/16532794.html
Author: new_monkey
Title: 算法：斐波那契数列
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/605177/
转载文章受原作者版权保护。转载请注明原作者出处！