👉题目：一只青蛙一次可以条一级台阶也可以一次跳两级台阶，如果有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)
}
}
}
