1、 subject ： Fibonacci number

Fibonacci number  （ Usually use  F(n) Express ） The sequence formed is called Fibonacci sequence . The sequence is composed of  0 and 1 Start , Each of the following numbers is the sum of the first two numbers . That is to say ：

F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2), among n > 1
Given  n , Please calculate F(n) .

2、 Their thinking

Five steps of dynamic planning

1、 determine dp The meaning of arrays and subscripts , The first i The Fibonacci value of the number is dp[i]

2、 Determine the recurrence formula , State transition equation dp[i] = dp[i - 1] + dp[i - 2];

3、dp How to initialize an array , How to initialize is also directly given to us in the topic

dp[0] = 0;
dp[1] = 1;

4、 Determine the traversal order , From recursive formula dp[i] = dp[i - 1] + dp[i - 2]; It can be seen that ,dp[i] It's dependence dp[i - 1] and dp[i - 2], Then the traversal order must be from front to back

5、 Give an example to deduce dp Array , According to this recurrence formula dp[i] = dp[i - 1] + dp[i - 2], Let's deduce , When N by 10 When ,dp The array should be the following sequence ：0 1 1 2 3 5 8 13 21 34 55

3、 Code

class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        vector<int> dp(N + 1);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[N];
    }
};