题解 | #斐波那契数列#

class Solution {
public:
    int Fibonacci(int n) {
        if(n == 1 || n== 2){
        return 1;
        }

        int a = 1;
        int b = 1;
        int temp = 0;
        for (int i = 3; i <= n; i++) {
            temp = (a + b)% 1000000007;
            a = b;
            b = temp;
        }
        return temp;
    }
};

动态规划有几个典型特征，最优子结构、状态转移方程、边界、重叠子问题。

在Fibonacci问题中：

f(n-1)和f(n-2) 称为 f(n) 的最优子结构

f(n)= f（n-1）+f（n-2）就称为状态转移方程

f(1) = 1, f(2) = 2 就是边界

比如f(7)= f(6)+f(5),f(6) = f(5) + f(4) ,f(5)就是重叠子问题。

我们来看下自底向上的解法，从f(1)往f(10）方向，想想是不是直接一个for循环就可以解决啦，如下：