这篇文章主要介绍LeetCode如何求斐波那契数列的第n项,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!
问题简述
写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:
F(0) = 0, F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1.斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例
示例 1:输入:n = 2输出:1示例 2:输入:n = 5输出:5
题解思路
使用动态规划的方式进行解决
题解程序
public class FibTest { public static void main(String[] args) { int n = 5; int a = fib(n); System.out.println("a = " + a); } public static int fib(int n) { if (n == 0) { return 0; } if (n == 1) { return 1; } int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; dp[i] = dp[i] % 1000000007; } return dp[n]; }}
题解程序图片版
以上是“LeetCode如何求斐波那契数列的第n项”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/3934278/blog/4679658