写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
在没有接触动态规划解法之前，首先想到的就是递归。通过递归 n-1 ,直到 n 为 0、1 的特值。
直接递归
- 原理： 把 f(n)f(n) 问题的计算拆分成 f(n-1)f(n−1) 和 f(n-2)f(n−2) 两个子问题的计算，并递归，以 f(0)f(0) 和 f(1)f(1) 为终止条件。
- 缺点： 大量重复的递归计算，例如 f(n)f(n) 和 f(n - 1)f(n−1) 两者向下递归需要 各自计算 f(n - 2)f(n−2) 的值。
func fib(_ n: Int) -> Int {
if (n == 0) {
return 0
}
if (n == 1) {
return 1
}
return fib(n-1) + fib(n-2)
}
好吧，如果你用这个代码提交到力扣上，直接gg。这种方法太过耗时了。
。
树中存在很多重复的节点，算法中存在很多重复的计算量。优化策略：我们可以将算好的结果缓存起来，如果下次碰到一样的计算项时，我们先可以查找缓存。如果查不到在去计算。会大大的节省计算时间。
记忆化递归
我们可以使用O(n)的空间来存放计算的结果，每次计算可以查找到之前结果，不用重新计算。
func fib(_ n: Int) -> Int {
if (n == 0) {
return 0
}
if (n == 1) {
return 1
}
var cache = [Int](repeating: 0, count: n+1)
cache[1] = 1
for i in 2...n {
cache[i] = cache[i-1] + cache[i-2]
}
return cache[n]
}
动态规划
我们也可以通过动态规划来解决这道问题。目前留个坑，学完动态规划在回来解决。
