Now please don't go downvoting the blog as there already are blogs and editorials on this, I know, please read my question though

So, I solved this problem using a 2d dp — `dp[n][2]`

which was the solution I found in almost all of the editorials and blogs. But here's something interesting my friend found,

`dp[i] = 6*dp[i-1] - 7*dp[i-2]`

Apparently this recursive relation also solves the problem...

So, does anybody have an intuition for this?

I found it here

I would also like to tag the person who wrote this code — Jonathan_Uy