dynamic programming solution for a string ending with 0, 1 or 2

Question

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][2]
    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))

Answer 1

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 <= 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