A string that contains only `0s`, `1s`, and `2s` is called a ternary string. Find a total ternary strings of length `n` that do not contain two consecutive `0s` or two consecutive `1s`.

I have defined a recurrence relation as `dp[i][j]` means the total number os trings ending with `j` where `i` is the length of the string and `j` is either `0`, `1` or `2`.

dp[i][0] = dp[i-1][1] + dp[i-1][2]

dp[i][1] = dp[i-1][0] + dp[i-1][2]

dp[i][2] = dp[i-1][1] + dp[i-1][2] + dp[i-1][1]

    from collections import defaultdict

    def end_with_x(n):
      dp = defaultdict(int)
      dp[1] = defaultdict(int)
      dp[1][0] = 1
      dp[1][1] = 1
      dp[1][2] = 1
      for i in range(2, n+1):
        dp[i] = defaultdict(int)
        dp[i][0] = dp[i-1][1] + dp[i-1][1]
        dp[i][1] = dp[i-1][0] + dp[i-1][2]
        dp[i][2] = dp[i-1][2] + dp[i-1][0] + dp[i-1][1]
      return dp[n][0] + dp[n][1] + dp[n][2]
    print(end_with_x(2))