Давайте хранить, сколько существует строк длины k заканчивающихся на 0, на 1, на 2. dp[k][0] -- кол-во строк длины k, заканчивающихся на 0, dp[k][1] -- кол-во строк длины k, заканчивающихся на 1, dp[k][2] -- кол-во строк длины k, заканчивающихся на 2.

Заполним базу динамики -- у нас 1 строка длины 1, заканчивающаяся на 0; 1 строка длины 1, заканчивающаяся на 1; 1 строка длины 1, заканчивающаяся на 2:
dp[1][0] = 1
dp[1][1] = 1
dp[1][2] = 1

Продумаем переход:
0 мы можем приписать к любой строке, получается что dp[k + 1][0] = dp[k][0] + dp[k][1] + dp[k][2]
1 мы можем приписать только к строкам, которые оканчиваются на 0 или 2, получается что dp[k + 1][1] = dp[k][0] + dp[k][2]
2 мы можем приписать к любой строке, получается что dp[k + 1][2] = dp[k][0] + dp[k][1] + dp[k][2]

Ответ будет лежать в dp[n][0] + dp[n][1] + dp[n][2]. Все возможные строчки, заканчивающиеся на 0 или 1 или 2.