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

If a frog jumps up n steps, it can only jump up (n-1) or (n-2).

Solution 1: dynamic programming solution

var numWays = function(n){
    if(n == 0)    return 1;
    var i = 0;
    var pre = 0;
    var current = 1;
    var result = 0;
    while(i++ < n){
        result = (pre + current)%1000000007;
        pre = current;
        current = result;
    }
    return result;
}
Copy the code

Solution two: dynamic programming + array memory

var numWays = function(n){
    var a = 0, b = 1;
    while(n--){
        [a,b] = [b,(a+b)%1000000007]
    }
    return b;
}
Copy the code