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

• s3bw: Can I suggest writing that line as: n0, n1, n2 = (n1 + n2), (n0 + n2), (n0 + n1 + n2)
• YvesgereY: @foxyblue You can!