dp[i][j] - amount of i-digit numbers ending with j.

therefore we form 2d table dp[n][2]

then

dp[i][0] = dp[i - 1][0] + dp[i - 1][1]
dp[i][1] = dp[i - 1][1]

It's not hard to see that dp[i][0] + dp[i][1] (i.e. number of all valid sequences) forms a fibonacci sequence.

dp[i][0] + dp[i][1] = 2*dp[i - 1][0] + dp[i - 1][1]
you can treat as f_n = 2*f_(n - 2) + f_(n - 3)

But still, I don't know how to solve this problem :)

Edited by author 23.01.2022 01:36

Edited by author 23.01.2022 01:37

dp[i][1] = dp[i - 1][1] is wrong, should be:
dp[i][1] = dp[i - 1][0]