dynamic programming solution for a string ending with 0, 1 or 2
Your recurrence is very fine, so I've just minor adjustments to propose:


In this kind of bottom-up DP, you only need to access the previous row. No need to keep the whole history.
There is a copy/paste bug in dp[i][0] computation.
No need to use a dict, each level (row) is fully filled out.


I would thus write:

def total_with_length(n):
    if n &lt;= 0:
        return 0
    n0, n1, n2 = 1, 1, 1
    for _ in range(n-1):
        n0, n1, n2 = n1+n2, n0+n2, n0+n1+n2
    return n0 + n1 + n2