??題目：一只青蛙一次可以條一級(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)
}
}
}
