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