Re: i solved dp[i] - the number of sequences of length i

Posted by

Ivan 23 Jan 2022 01:33

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*

Re: i solved dp[i] - the number of sequences of length i

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

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