“This is the 35th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

I. Problem description

A frog can jump up one step or two steps at a time. Find the total number of jumps the frog can take up a step of n (0 <= n <= 100).

1e9+7 (1000000007) is required for the answer. If the initial calculation result is 1000000008, return 1.

Two, the title requirements

Operating limits

  • Maximum running time: 1s
  • Maximum running memory: 128M

The sample

Input: 2 Output: 2 Output: 7 Output: 21 Input: 0 Output: 1Copy the code

inspection

1. Getting started 2. You are advised to use 5 to 15 minutesCopy the code

Third, problem analysis

I haven’t done a lot of dynamic programming before, so this one is kind of a primer, so I’m going to go into dynamic programming as much detail as possible. We’re going to talk about dynamic programming.

Dynamic planning takes a few steps, like an elephant in a refrigerator, divided into three:

Step 1: Get the meaning

Dynamic programming usually uses the array dp[] to store things. What exactly is stored in the array?

Dp [I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I]

Step 2: Variable initialization

Dp [0]=1 Dp [1]=1 1 step to DP [2]=2 2 steps can be taken one step and then one step, or two steps can be taken at a time, so the two solutions dp[3]=3 3 steps at a time, one step and then two steps, two steps and then one step......Copy the code

Initial variables generally find 2~5 on the line, the following is the highlight!

Step 3: Relational induction

So if we know what the array means and what the initial value is, we’re going to find the number of NTH steps, and they didn’t give us that, so what do we do?

Look for rules, make a summary, and see what relationship there is with the front step scheme, this step is very important, the law is not looking for direct Barbie Q.

Take a closer look at the rule of step 2. Is the latter equal to the sum of the first two, so the NTH formula is:

Dp [n] = dp [n – 1) + dp (n – 2).

Three steps, call it a day!

Four, coding implementation

#include<iostream>
using namespace std;
int numWays(int n)
{
    if(n<=1) return 1;
    int dp[n+1],i;
    dp[0] =1,dp[1] =1;// Initialize variables
    for(i=2; i<=n; i++) {/ / law
        dp[i]=(dp[i- 1]+dp[i2 -]) %1000000007;// Don't forget to take the mold
    }
    return dp[n];// Return the result
}
int main(a)
{
	int k;
	cin>>k;// Enter the number of steps
	cout<<numWays(k);// The function assigned to the dynamic programming function
	return 0;
}
Copy the code

V. Test results

Sixth, summary and improvement

If the title is:

A frog can jump up one step at a time, or two steps…… All the way to the n steps. Find out how many ways the frog can jump up a step of n (0 <= n <= 100) steps, and share the results in the comments section.