编辑代码

//import Cocoa
//
//var greeting = "Hello, playground"
//print(greeting)

// 自选题目，递归和动态规划解决斐波那契数列问题，要求递归要剪枝
// 算法思路
// 程序代码
// 测试样例
func fibonacci(_ n: Int) -> Int {
    if n <= 1 {
        return n
    }
    return fibonacci(n-1) + fibonacci(n-2)
}

func fibonacciDP(_ n: Int) -> Int {
    var fibArray = [0, 1]
    if(n>=2){
        
    for i in 2...n {
        fibArray.append(fibArray[i-1] + fibArray[i-2])
    }
    }
    return fibArray.last!
}

func testFibonacci() {
    // 递归形式测试用例
    print(fibonacci(0)) // 输出 0
    print(fibonacci(1)) // 输出 1
    print(fibonacci(2)) // 输出 1
    print(fibonacci(3)) // 输出 2
    print(fibonacci(4)) // 输出 3
    print(fibonacci(5)) // 输出 5
    print(fibonacci(6)) // 输出 8
    print(fibonacci(7)) // 输出 13
    print(fibonacci(8)) // 输出 21
    print(fibonacci(9)) // 输出 34
    print(fibonacci(10)) // 输出 55
    print("-------")
    print("DP")
    print("-------")
    
    print(fibonacciDP(0)) // 输出 0
    print(fibonacciDP(1)) // 输出 1
    print(fibonacciDP(2)) // 输出 1
    print(fibonacciDP(3)) // 输出 2
    print(fibonacciDP(4)) // 输出 3
    print(fibonacciDP(5)) // 输出 5
    print(fibonacciDP(6)) // 输出 8
    print(fibonacciDP(7)) // 输出 13
    print(fibonacciDP(8)) // 输出 21
    print(fibonacciDP(9)) // 输出 34
    print(fibonacciDP(10)) // 输出
    
}

testFibonacci()