Brush the title "sword finger offer" day03

Title source ： Power button 《 The finger of the sword Offer》 The second edition
Completion time ：2022/07/24

10- I. Fibonacci sequence

My explanation

class Solution {
    
public:
    int fib(int n) {
    
        if(n == 0 || n == 1){
    
            return n;
        }
        int a = 0,b = 1,count = 1;
        while(count != n){
    
            int res = (a + b) % 1000000007;
            a = b;
            b = res;
            count++;
        }
        return b;
    }
};

10- II. The problem of frog jumping on the steps

My explanation

This problem is almost the same as Fibonacci series , At first I didn't think of it , Read the solution in the book . You can choose to jump every time you jump on the steps 1 Grade or 2 level , therefore n The jumping method of steps is f(n-1) + f(n-2) Kind of . Except for the initial f(0) Not the same , All the others can be applied to the previous question .

class Solution {
    
public:
    int numWays(int n) {
    
        if(n == 0 || n == 1){
    
            return 1;
        }
        int a = 1,b = 1,count = 1;
        while(count != n){
    
            int res = (a + b) % 1000000007;
            a = b;
            b = res;
            count++;
        }
        return b;
    }
};