5、动态规划---斐波那契数列

题目描述：f(0) = 0, f(1) = 1，f(n) = f(n - 1) + f(n - 2), 其中 n> 1。答案需要取模
     1e9+7（1000000007）

 public int fib(int n) {
        int a = 0, b = 1, sum;
        for(int i = 0; i < n; i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }

动态规划算法即

• 对于一个规模为n的问题，将其分解为k个规模较小的子问题（阶段），按顺序求解子问题，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，通过决策求得局部最优解，依次解决各子问题。最后可以通过简单的判断，得到原问题的解。