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]

1 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
  • \$\begingroup\$ Can I suggest writing that line as: n0, n1, n2 = (n1 + n2), (n0 + n2), (n0 + n1 + n2) \$\endgroup\$
    – foxyblue
    Nov 10, 2017 at 11:44
  • \$\begingroup\$ @foxyblue You can! \$\endgroup\$
    – YvesgereY
    Sep 7, 2019 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.