Programming problem - BLOCKS GAME PROBLEM


Problem Description: You are given a game of blocks. In this game you are given a grid of size 3 * N. You have to fill this grid with smaller blocks of size 1 * 2 (or 2 * 1 if rotated). Your task is to find the different number of ways to fill the grid. NOTE : Any two configurations are said to be different if the placement of at-least one block if different.

I/P format : First line denotes N htat is the grid size

Example 1: N=6 output : 41

Example 2: N=2 output : 3 (Total of 3 ways to fill the grid of size 3*N 1. AA BB CC 2. AA BC BC 3. AB AB CC) where A,B,C represent diff blocks

Anyone please help in this ques. No idea how to proceed any approach . Please provide code with explanatiion