Frog jump step problem

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

The title

A frog can jump up one step or two steps at a time. Find out how many ways the frog can jump up n steps.

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

Example 1:

Input: n = 2 Output: 2Copy the code

Example 2:

Input: n = 7 Output: 21Copy the code

Example 3:

Input: n = 0 Output: 1Copy the code

Tip:

0 <= n <= 100

Subject analysis

If n steps have f (n) jumps, if the last step is one step, then f (n-1) jumps, if the last step is two steps, then F (n-2) jumps, then f (n-1) + F (n-2) jumps, So f(n + 1) = f(n) + f(n – 1), that’s the Fibonacci sequence, that’s the Fibonacci sequence.

Code implementation

class Solution {
    public int numWays(int n) {
        int a = 1, b=1, sum;
        for (int i = 0; i<n; i++) { sum = (a + b)%1000000007;
            a = b;
            b = sum;
        }
        returna; }}Copy the code

This is I use a Java implementation of the function, the solution to every problem with different and writing, I generally adjusted and then wrote of his thoughts, also didn’t think about the other way, if you have a better solution, welcome and I leave a message, we progress together, learning data structure together, make progress together, through the problem can be more familiar with the Fibonacci sequence operation.

The seemingly difficult problems, after our analysis, are found to be simple Fibonacci sequence, which solves complex problems into familiar problems.

conclusion

This problem is also examining the thought of dynamic planning, the key to solve this kind of problem is to find a few problems and the relationship to the original question, regularities, problems are easily solved, finally demanded by the title, we don’t forget to take over the operation, these are the details to solve the problem, if not paying attention to details in place, the title of the answer is wrong, It will not be approved.

This problem first analysis here, if there is inappropriate, welcome to correct.

Frog jump step problem