👉题目：一只青蛙一次可以条一级台阶也可以一次跳两级台阶，如果有n级台阶青蛙有多少种跳法？🤔

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, ...
R1 = 1
R2 = 1
Rn = Rn-1 + Rn-2 (n>=3)

class LeetCode_FrogJump {
    
    func jump() {
        let target = 50
        print(_frogJump1(target))
        print(_frogJump2(target))
    }
    
    //方案2: 将方法递归转换为数组 时间复杂度O(1)
    func _frogJump2(_ target: Int) -> Int64 {
        
        var array:[Int64] = Array(repeating: 0, count: target+3)
        array[0] = 0
        array[1] = 1
        array[2] = 2
        if target >= 3 {
            for i in 3...target {
                array[i] = array[i-1]+array[i-2]
            }
        }
        return array[target]
    }
    
    //方案1: 方法递归超级好性能
    func _frogJump1(_ target: Int) -> Int64 {
        if target == 1 {
            return 1
        } else if target == 2 {
            return 2
        } else {
            //性能差。。。
            return _frogJump1(target-1)+_frogJump1(target-2)
        }
    }
}