509.Fibonacci_Number.md

509. Fibonacci Number

Problem statement:

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

Iterative solution:
Using two variables to iterate continuously to find the target.
Time complexity is O(n), Space complexity is O(n).

func fib(n int) int {
	if n <= 1 {
		return n
	}
	a, b := 0, 1
	for i := 2; i <= n; i++ {
		a, b = b, a+b
	}
	return b
}

1137. N-th Tribonacci Number

Same as Fibonacci number, but the formula is F(n) = F(n - 1) + F(n - 2) + F(n - 3).

Recursive solution:

func tribonacci(n int) int {
    switch n {
        case 0:
            return 0
        case 1:
            return 1
        case 2:
            return 1
        default:
            return recursive(0, 1, 1, 3, n)
    }
    return -1
}

func recursive(a, b, c, depth int, target int) int {
    if depth == target {
        return a + b + c
    }
    return recursive(b, c, a+b+c, depth+1, target)
}