Sword finger offer frog jumps stairs

Title Description

A frog can jump up at a time 1 Stepped steps , You can jump on it 2 level …… It can also jump on n level . Ask the frog to jump on one n How many jumps are there in the steps .（ Abnormal jump stairs ）

Their thinking

1. Mathematical induction

because n Stepped steps , The first step is n Jump ： jump 1 level 、 jump 2 level 、 To jump n level
jump 1 level , be left over n-1 level , The rest of the jump is f(n-1)
jump 2 level , be left over n-2 level , The rest of the jump is f(n-2)
therefore f(n)=f(n-1)+f(n-2)+…+f(1)
because f(n-1)=f(n-2)+f(n-3)+…+f(1)
therefore f(n)=2*f(n-1)
Calculate directly according to the formula , Write recursion

2. Brute force

jump 10 Stairs , It can be divided into jumping 1 individual , jump 2 All the way to jump 10 individual , So the cycle .
If you jump one , There's more left 9 individual , Run recursively , Nine can be divided into jumps 1 Jump nine , Until if there is only one staircase left , Just go back to 1. In fact, these two ideas are essentially the same , Just the last one is calculating from 1 Jump to the n A formula is used in the addition of, while brute force cracking uses a loop , For example, I jump 10 individual , Will calculate from f（1） Add to f（9） Of , But the formula is calculated directly f（10）=2*f(10-1)

public class Solution {
    
    public int JumpFloorII(int target) {
    
        if(target==1){
    
            return 1;
        }
        int temp=0;
        for(int i =1;i<target;i++){
    
            temp=temp+JumpFloorII(i);
        }
        return temp+1;
    }
}