Coin Problem: Let’s code 2.0

Find link to problem here

Problem statement

A coin is tossed ’n’ times find the number of combinations such that there is no 3 consecutive tails ‘TTT’

example n = 4

there are 2⁴ ways but we have to exclude HTTT, TTTH, and TTTT.

This can be done with 2D dp or a 1D dp

I’ll be explaining the 2D dp solution here .

CASE 1 i’th position is T:

So you are at i’th toss and you’ve got a T. Now you can fill the i-1 with a T which does not have a T beside it, meaning at i-2 th poisition.

Or you can have an H beside you and you don’t care whats beside it. The state position i with T having no T’s beside can be represented by dp[i-1][0] and with an H beside the T lets represent by dp[i-1][3] and let dp[i][2] represent answer to i’th position ending with T.

so dp[i][2] = dp[i-1][0] + dp[i-1][3];

CASE 2i’th position is H:

So you are i and you’ve got an H. Now you can have a i-1 th having a T with 0 T’s beside it or you can have i-1 th with a T having 1T beside it. but not 2T since that’ll make it 3T’s we don’t want that. Also we can have and H at i-1.

let’s represent a i’th position ending at T with 1T beside it as dp[i][1]

so i ending at H dp[i][3] = dp[i-1][1] + dp[i-1][0] + dp[i-1][3];

Update

Now we need to update dp[i][0] and dp[i][1] meaning i’th position with T having 0'T beside it and 1T beside it.

For dp[i][0] its = dp[i-1][3]; meaning the previous was an H. And

dp[i][1] = dp[i-1][0] the previous guy is a T having H beside it. Meaning you are a T with just 1T next to you.

pre compute dp states for n=1000000. And answer queries in O(1) time;

Make sure to mod your equation properly to pass all test cases.

        for(int i = 2; i <= n ;i++)
        {
            //T
            dp[i][2] = dp[i-1][0] + dp[i-1][3];
            
            //H
            dp[i][3] = dp[i-1][0] + dp[i-1][1] + dp[i-1][3];
            
            //update
            dp[i][0] = dp[i-1][3];
            dp[i][1] = dp[i-1][0];
        }

Thanks for reading :)

Also check out something that I made recently https://github.com/dragonzurfer/quickchat star it if you like it.