Sword finger offer:[day 8 dynamic planning (simple)] --- > frog jumping on steps

---

One 、 Title Description

A frog can jump up at a time 1 Stepped steps , You can jump on it 2 Stepped steps . Ask the frog to jump on one n How many jumps are there in the steps .
The answer needs to be modelled 1e9+7（1000000007）, If the initial result of calculation is ：1000000008, Please return 1.

Example 1：

 Input ：n = 2
 Output ：2

Example 2：

 Input ：n = 7
 Output ：21

Example 3：

 Input ：n = 0
 Output ：1

Tips ：
0<=n<=100

Two 、 Thought analysis

notes ： Some contents and pictures in the train of thought analysis refer to the solutions of your predecessors , Thank them for their selfless dedication

Ideas

Let's jump up n The steps have f(n) Jump . Of all the jumps , There are only two situations for the frog's last step ： Jump on 1 Grade or 2 Stepped steps .
When it comes to 1 Stepped steps ： Remnant n-1 A stair , There are a total of f(n-1) Jump
When it comes to 2 Stepped steps ： Remnant n-2 A stair , There are a total of f(n-2) Jump
f(n) Is the sum of the above two situations , namely f(n)=f(n-1)+f(n-2), The above recurrence property is Fibonacci sequence . This problem can be transformed into finding the number of Fibonacci n Item value , The only difference is that the starting number is different .
The problem of frog jumping on the steps ：f(0)=1,f(1)=1,f(2)=2
Fibonacci series question ：f(0)=0,f(1)=1,f(2)=1

Complexity analysis ：
Time complexity $\mathrm{O}(\mathrm{N})$： Calculation f(n) Need circulation n Time , The calculation operation in each cycle uses O(1)
Spatial complexity $\mathrm{O}(1)$： Several flag variables use constant size extra space

3、 ... and 、 The overall code

The overall code is as follows

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

function , The test passed