This problem is basically Climbing Stairs but using three states instead.
def tribonacci(n): if n == 0: return 0 # base case t0, t1, t2 = 0, 1, 1 for i in range(3, n + 1): t0, t1, t2 = t1, t2, t0 + t1 + t2 return t2
Last updated 4 months ago
As discussed in Climbing Stairs, since we only rely on the past 3 states, we can use nnn state caching and store them as variables instead.
3