斐波拉切数列 java版本
试求Fibn
样例
输入：
5
输出：
5
算法1
public class Solution { public static void main(String[] args) { Solution solution = new Solution(); int n = 10; int x = solution.fib(n); System.out.println(x); } public int fib(int n) { if (n == 0 || n == 1) { return n; } 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] ) % 1000000007; } return dp[n] % 1000000007; } }
算法2
(暴力递推+空间优化) O(n)
代码如下：
public class Solution { public static void main(String[] args) { Solution solution = new Solution(); int n = 10; int x = solution.fib(n); System.out.println(x); } public int fib(int n) { if (n == 0 || n == 1) { return n; } int a = 0; int b = 1; int c = 0; for (int i = 2; i <= n; i++) { c = (a + b) % 1000000007; a = b; b = c; } return c % 1000000007; } }
算法3
(求递推公式) O ( 1 ) O(1)O(1)
我慢慢要显露出数竞生本色啦！
要讲明白特征方程是怎么回事实在是太麻烦了，笔者手写了三页，但最后字迹过于丑陋，不宜展示。
我认为这里写的不错，可以参考。
综上，通项公式为：
借鉴 https://www.acwing.com/solution/content/12476/
代码
class Solution { public int Fibonacci(int n) { double a = (1 + Math.sqrt(5)) / 2; double qa = Math.pow(a,n); double b = (1 - Math.sqrt(5)) / 2; double qb = Math.pow(b,n); double res = ( (1 / Math.sqrt(5)) * (qa - qb) % 1000000007); return (int)res; } }
