【LeetCode】剑指 Offer 10- I. 斐波那契数列

文章目录

【LeetCode】剑指 Offer 10- I. 斐波那契数列一、递归二、递归+哈希表三、动态规划总结

一、递归

二、递归+哈希表

三、动态规划

需要注意一点，取余必须写在循环内，否则超出范围之后再怎么取余都是对错误的结果取余，那么取余的结果肯定也是错的

class Solution {public int fib(int n) {if(n == 0){return 0;}else if(n == 1){return 1;}int f0 = 0;int f1 = 1;int res = 0;for(int i = 2; i <= n; i++){res = (f0 + f1)% 1000000007;f0 = f1;f1 = res;}return res ;}}

时间复杂度 O(n)：计算 f(n) 需循环 n 次，每次循环内操作时间复杂度为 O(1)空间复杂度 O(1)：几个标志变量使用常数大小的额外空间

---

总结

很简单的动态规划题，参考【Java数据结构与算法】第十八章