CareerCup

looks like this is A127864 or A077917 from oeis.org
According to this reference, the formula is:
F(i) = F(i-1) + 4 * F(i-2) + 2 * F(i-3).

c# implementation.

static private long GetNumberOfCombinations( int n ) {

    if ( n <= 0 ) return 0;

    long[] seq = { 1, 5, 11 }; // initial items of the sequence, they cannot be calculated, they are obtained empirically.

    if ( n < seq.Length + 1 ) {
        return seq[ n - 1 ];
    }
            
    for ( int i = seq.Length; i < n; i++ ) {
        var res = seq[ 2 ] + 4 * seq[ 1 ] + 2 * seq[ 0 ];
        seq[ 0 ] = seq[ 1 ];
        seq[ 1 ] = seq[ 2 ];
        seq[ 2 ] = res;
    }
    return seq[ 2 ];
}

Actually it's A005178 from oeis.org.
The formula is
F(0) = 1, F(1) = 1, F(2) = 5, F(3) = 11 and
F(n) = F(n-1) + 5F(n-2) + F(n-3) - F(n-4) for n>3.
In particular, F(4) is 36, not 33.

I think it is 3N + 4(N-1) = 7*N-4

F(i) = F(i + 1) + 4 * F(i + 2)

F[N] = 1
F[N - 1] = 4
for (i = N - 2 ; i >= 0; --i)  {
 	F[i] = F[i + 1] + 4 * F[i + 2];
}

return F[0];

@zr.roman How did you figure out that the answer will be found from the fibnacci sequence?

According to your solution, the answer for 4*1 block is 3, but shouldn't it be 1?

No, it is something different.
By empirical way I discovered the following first answers:
n = 1, answer = 1.
n = 2, answer = 5.
n = 3, answer = 11.
n = 4, answer = 33.
So, what rule could it be?

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		System.out.println(new Codechef().getNoWays(29));
	}
	
	public int getNoWays(int length){
	    return getNoWays(length, false);
	}
	private Map<Integer, Integer> cache = new HashMap();
	private int getNoWays(int length, boolean isLowerOccupied ){
	    if(cache.containsKey(length))
	        return cache.get(length);
	    if(length == 0 || length == 1){
	        cache.put(length, 1);
	        return 1;
	    }
	    int noWays = 0;
	    if(isLowerOccupied){
	        noWays = getNoWays(length-2, false);
	    }
	    else{
	        noWays = getNoWays(length-1, false) + getNoWays(length, true);
	        System.out.println("Evaluated for " + length + " - " + noWays);
	        cache.put(length, noWays);
	    }
	    return noWays;
	}
}

for @kanon
looks like, you are wrong.
"uploads.ru/AORLC.jpg"
Here I draw all the 33 variants for F(4). Look.
If I missed something, please, let me know.

This is the same problem as problem code 'GNY07H' on SPOJ.

This is how the recursive function will look like:

f(n) = f(n-2) + f(n-1) + 6;

When we cut one block of width 1, then there is only one way to fill it using 2*1 blocks. i.e two of 1*2 vertical block one above the other.

When we cut one block of width 2, then there are 5 ways to fill it using 2*1 blocks. Shown below.

a. All 2*1 blocks lying horizontally on top of each other.
b. Two 2*1 blocks lying horizontally and 2 on top of them vertically.
c. Vice Versa of above case.
d. One 2*1 block lying horizontally then 2 on top of it vertically and then another one on top of them horizontally.
e. 2*1 blocks all standing vertically.

Hence at any point we can either choose to reduce width by 1 block (1 way) or by 2 blocks (5 way) giving:

f(n) = f(n-1) + 1 + f(n-2) + 5 = f(n-1) + f(n-2) + 6.

Solve it using DP now.

this is a Fibonacci sequence task,
the answer is 34 if n = 4.
For the other values of n, we should take the respective value from Fibonacci sequence.