leetcode refers to Offer 10- II. Frog jumping steps

A frog can jump up 1 or 2 steps at a time.Find how many ways the frog can jump up a n steps.

The answer needs to be modulo 1e9+7 (1000000007). If the initial calculation result 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
Prompt:

0 <= n <= 100

Thinking:

In fact, the idea of ​​​​the Fibonacci sequence is the same. There are f(n-1) and f(n-2) methods to reach the nth step.

It is enough to jump once from the n-1th to the nth order, so there is only one way, and from the n-2 to the nth order, you can jump 2 orders at a time or jump 2 times at a time, and thenThe first one (the method of jumping one order at a time) has been counted in the method from n-1 to the nth order.

So from n-2 to the nth order there is only one way to jump to order 2.

So f(n) = f(n-1)+f(n-2)

class Solution {public:int numWays(int n) {/*int a=1,b=2; //The code commented out here uses dynamic programming int h; for(int i=2;i<=n;++i){ h=a+b; h%=1000000007; a=b; b=h; } return a; */if(n<=1)return 1;int dp[n+1];dp[1]=1;dp[2]=2;for(int i=3;i<=n;++i){dp[i]=dp[i-1]span>+dp[i-2]; //hereUse arrays to store values ​​and avoid repeated operationsdp[i]%=1000000007;}return dp[n];}};