??題目：一只青蛙一次可以條一級(jí)臺(tái)階也可以一次跳兩級(jí)臺(tái)階，如果有n級(jí)臺(tái)階青蛙有多少種跳法？??

斐波那契數(shù)列：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: 將方法遞歸轉(zhuǎn)換為數(shù)組 時(shí)間復(fù)雜度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: 方法遞歸超級(jí)好性能
    func _frogJump1(_ target: Int) -> Int64 {
        if target == 1 {
            return 1
        } else if target == 2 {
            return 2
        } else {
            //性能差。。。
            return _frogJump1(target-1)+_frogJump1(target-2)
        }
    }
}