Like Fibonacci, but with three numbers instead of two.
The solution is as follows:
class Solution:
def tribonacci(self, n: int) -> int:
if n < 3:
return 1 if n else 0
a, b, c = 0, 1, 1
for _ in range(3, n + 1):
a, b, c = b, c, a + b + c
return c_ Time Complexity:
O(n) - Where n is the input number, we iterate n times.
_ Space Complexity:
O(1) - We use three integers variables, taking constant space to memoize the three numbers for the Tribonacci sequenece.