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
Make all the configurations for n = 2, and see how you can extend it to n = 3. I'm able to get the given recurrence relation but since it involves lots of drawing its really hard to explain it here.