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

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


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

• Can I suggest writing that line as: n0, n1, n2 = (n1 + n2), (n0 + n2), (n0 + n1 + n2) Nov 10, 2017 at 11:44
• @foxyblue You can! Sep 7, 2019 at 11:46