Swift.斐波那契额数列

题目描述：求斐波那契数列的第 n 项。

import Foundation

class For09Solution {
    func Fibonacci(_ n: Int) -> Int {
        if n <= 0 {
            return 0
        }
        
        if n == 1 {
            return 1
        }
        
        if  n > 1 {
            return Fibonacci(n-1) + Fibonacci(n-2)
        }
        
        return 0
    }
    
    
    func Fibonacci2(_ n: Int) -> Int {
        
        if n == 0 {
            return 0
        }
        
        if n == 1 {
            return 1
        }
        
        var lastlast = 0
        var last = 1
        var res = 0
        for i in 0..<n+1 {
            if i > 1 {
                res = last + lastlast
                lastlast = last
                last = res
            }
        }
        
        return res
    }
}

算法思想：如果使用递归求解，会重复计算一些子问题。例如，计算 f(4) 需要计算 f(3) 和 f(2)，计算 f(3) 需要计算 f(2) 和 f(1)，可以看到 f(2) 被重复计算了。
递归是将一个问题划分成多个子问题求解，动态规划也是如此，但是动态规划会把子问题的解缓存起来，从而避免重复求解子问题。

github地址：https://github.com/cubegao/LeetCode