A, the title

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

The answer should be modulo 1e9+7 (1000000007). If the initial result is 1000000008, return 1.

Sample 1:

Input: n = 2 Output: 2Copy the code

Example 2:

Input: n = 7 Output: 21Copy the code

Sample 3:

Input: n = 0 Output: 1Copy the code

Tip:

0 <= n <= 100

Second, the answer key

So this is a little confusing, but I think this is a very complicated problem, so let’s say they ask you how many different ways a frog can jump up an n-step. So let’s say the frog jumps up 0 steps and there are several ways to jump, obviously one, because they all involve jumping. There are several ways to jump up a 1 step. It is also a kind, because it is ok as long as you jump up 1 step. What about the two steps? Here are two kinds, one kind is jump two grade 1, one kind is to jump a level 2, then we abstract thinking, and jumped on to the final step in n level there are several, two kinds, one kind is in the n – 1 step jump level 1, one is in the n – 2 steps jump two stage, and then I continued steps and n o n – 1-2 steps have a few kinds of methods, recursive! So is this the recursion? And the formula is f(n)=f(n-1)+f(n-2), so the kernel of this problem is actually the Fibonacci sequence operation, but note that! The initial value is different! F (0) = 1, f (1) = 1.

So the solution is just like the Fibonacci problem. Links: juejin. Cn/post / 698720…

So what I’m going to do is just write some code for dynamic programming

3. Code (JS)

/ * * *@param {number} n
 * @return {number}* /

// The type is Fibonacci, but the initial data is different

// Dynamic programming
var numWays = function(n) {
  let dp = new Array(n+1);
  // Jumping up 0 steps is one method
  dp[0] =1;
  // There is only one way to jump up a step
  dp[1] =1;
  for(let i = 2; i <= n ; i++) { dp[i] = dp[i-1] + dp[i-2]; 
      dp[i]%=1000000007;
  }
  return dp[n];
};
Copy the code

4. Expand your thinking

The main thing is to focus on abstractions into concrete modes of thinking, and not much else.

Source: LeetCode link: leetcode-cn.com/problems/qi…