LeetCode – 1137. N-th Tribonacci Number

題目連結: https://leetcode.com/problems/n-th-tribonacci-number/

練習提問:

Q: n的range是? Ans: 0 ~ 37

法ㄧ(Recursive version) Time Limit Exceeded

    func tribonacci(_ n: Int) -> Int {
        if n == 0 { return 0 }
        else if n == 1 { return 1 }
        else if n == 2 { return 1 }
        else {
        	return tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3)
        }
    }

法二(Iterative version)

    func tribonacci(_ n: Int) -> Int {
        if n == 0 { return 0 }
        else if n == 1 { return 1 }
        else if n == 2 { return 1 }
        else {
        	var arr = Array(repeating: 0, count: n + 1)
        	arr[1] = 1
        	arr[2] = 1
        	for i in 3 ... n {
        		arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
        	}
        	return arr[n]
        }
    }

%d