前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >509. 斐波那契数

509. 斐波那契数

原创
作者头像
Michel_Rolle
修改2021-02-01 11:07:23
1.7K0
修改2021-02-01 11:07:23
举报
文章被收录于专栏:LeetCode解题LeetCode解题

509. 斐波那契数

链接

斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

代码语言:txt
复制
F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

给定 N,计算 F(N)。

示例1:

代码语言:txt
复制
输入:2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1.

示例2:

代码语言:txt
复制
输入:3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2.

示例3:

代码语言:txt
复制
输入:4
输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3.

提示:

  • 0 ≤ N ≤ 30

go语言

代码语言:txt
复制
func fib(N int) int {
	if N == 0 {
		return 0
	}

	if N <= 2 {
		return 1
	}

	n1, n2 := 1, 1 // n1为n-1,n2为n-2

	for i := 3; i < N; i++ {
		n1, n2 = n1+n2, n1
	}

	return n1 + n2

}

func fib2(n int) int {
       if n==0 ||n==1{
        return n
    }
    dp:=make([]int,n+1)
    dp[0]=0
    dp[1]=1
    for i:=2;i<=n;i++{
        dp[i]=(dp[i-1]+dp[i-2])%1000000007
    }
    return dp[n]
}

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 509. 斐波那契数
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档