unreasonably effective

link

We can use Dynamic Programming.

Sub-problem

solutions[i] = solutions[i-1] + solutions[i-2] + solutions[i-3]

Trivial sub-problems: solutions[0], solutions[1], and solutions[2]

Order

Since solutions[i] only depends on solutions[j] where j < i, we can process the sub-problems in increasing order of i and that would be a topologically sorted order.

class Solution:
    def tribonacci(self, n: int) -> int:
        dp = [0, 1, 1]
        if n < 3:
            return dp[n]
            
        m = n-2
        for _ in range(m):
            dp[0], dp[1], dp[2] = dp[1], dp[2], sum(dp)

        return dp[-1]