12-剑指offer10-1.斐波那契数列

题目描述：

解题思路：

看到题目的第一反应是递归，傻傻的写了两行代码，很明显超出了时间限制。

看题解说道记忆化递归法，在原有递归的基础上，新建了一个大小为n的数组，用于在递归时存储f(0)到f(n)的值，重复遇到某数字则直接从数组取用，避免了重复的递归计算。而事实上，最终的计算结果，只和第i项和第i-1项有关，因此只需要初始化三个整型变量sum,a,b即可，空间复杂度即可降为1。这里即是应用到了动态规划

代码：

class Solution {
    public int fib(int n) {
        int fib0 = 0;
        int fib1 = 1;
        int sum = 0;
        if(n == 0 || n == 1){
            return n;
        }
        for(int i = 2; i <= n; i++){
            sum = (fib0 + fib1) % 1000000007;
            fib0 = fib1;
            fib1 = sum;
        }
        return sum;
    }
}

12-剑指offer10-1.斐波那契数列

原文：https://www.cnblogs.com/forrestyu/p/14735923.html