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…