Sword finger offer 10- ii Frog jumping on steps

One 、 Reference material

The finger of the sword Offer 10- II. The problem of frog jumping on the steps

Interview questions 10- II. The problem of frog jumping on the steps （ Recurrence method ） subject

Two 、 subject

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

3、 ... and 、 analysis

use f(1) Indicates the number of paths to jump to the first step
use f(2) Indicates the number of paths to jump to the second step
use f(3) Indicates the number of paths to jump to the third step
use f(4) Indicates the number of paths to jump to the fourth step
use f(n) Jump to the n Number of paths for steps

f(1)： Just jump up . f(1) = 1.

f(2)： Want to jump to the second step , There are two ways ：
Method 1 ： Jump one step from the first step to . Yes f(1) Seed path
Method 2 ： Jump straight to the second step . There is a path . common f(1) + 1 = 2 Seed path .

f(3)： Want to jump to the third step , There are two ways ：
Method 1 ： Jump two steps from the first step to . Yes f(1) Seed path .
Method 2 ： Jump one step from the second step to . Yes f(2) Seed path . common f(1) + f(2) = 3 Seed path .

f(4)： Want to jump to the fourth step , There are two ways ：
Method 1 ： Jump two steps from the second step to . Yes f(2) Seed path .
Method 2 ： Jump one step from the third step to . Yes f(3) Seed path . common f(2) + f(3) = 5 Seed path .

f(5)： Want to jump to the fifth step , There are two ways ：
Method 1 ： Jump two steps from the third step to . Yes f(3) Seed path .
Method 2 ： Jump one step from the fourth step to . Yes f(4) Seed path . common f(3) + f(4) = 8 Seed path .

f(n)： I want to jump to number one n A stair , There are two ways ：
Method 1 ： From n-2 Jump two steps to . Yes f(n-2) Seed path .
Method 2 ： From n-1 Step by step to reach . Yes f(n-1) Seed path . common f(n-2) + f(n-1) Seed path .

Four 、 Refer to the answer

class Solution {
public:
    int numWays(int n) {
        if(n == 0) return 1;
        if(n <= 2) return n;
        int a = 1, b = 2, c = 0;
        for (int i = 3; i <= n; ++i) {
            c = (a + b) % 1000000007;
            a = b;
            b = c;
        }
        return c;
    }
};