Massive Algorithms: Count number of ways to fill a "n x 4" grid using "1 x 4" tiles

Count number of ways to fill a "n x 4" grid using "1 x 4" tiles - GeeksforGeeks
Given a number n, count number of ways to fill a n x 4 grid using 1 x 4 tiles.

Input : n = 4
Output : 2
The two ways are : 
  1) Place all tiles horizontally 
  2) Place all tiles vertically.

Let “count(n)” be the count of ways to place tiles on a “n x 4″ grid, following two cases arise when we place the first tile.

Place the first tile vertically: If we place first tile horizontally, the problem reduces to “count(n-1)”
Place the first tile horizontally: If we place first tile vertically, then we must place 3 more tiles vertically. So the problem reduces to “count(n-4)”

   count(n) = 1 if n = 1 or n = 2 or n = 3   
   count(n) = 2 if n = 4
   count(n) = count(n-1) + count(n-4)

int count(int n)

{

    // Create a table to store results of subproblems

    // dp[i] stores count of ways for i x 4 grid.

    int dp[n+1];

    dp[0] = 0;

    // Fill the table from d[1] to dp[n]

    for (int i=1; i<=n; i++)

{

        // Base cases

        if (i >= 1 && i <= 3)

            dp[i] = 1;

        else if (i==4)

            dp[i] = 2 ;

  else {

        // dp(i-1) : Place first tile horizontally

        // dp(n-4) : Place first tile vertically

        //           which means 3 more tiles have

        //           to be placed vertically.

        dp[i] = dp[i-1] + dp[i-4];

}

}

    return dp[n];

}

http://www.geeksforgeeks.org/tiling-problem/

Given a “2 x n” board and tiles of size “2 x 1″, count the number of ways to tile the given board using the 2 x 1 tiles. A tile can either be placed horizontally i.e., as a 1 x 2 tile or vertically i.e., as 2 x 1 tile.

Let “count(n)” be the count of ways to place tiles on a “2 x n” grid, we have following two ways to place first tile.
1) If we place first tile vertically, the problem reduces to “count(n-1)”
2) If we place first tile horizontally, we have to place second tile also horizontally. So the problem reduces to “count(n-2)”

Therefore, count(n) can be written as below.

   count(n) = n if n = 1 or n = 2
   count(n) = count(n-1) + count(n-2)

The above recurrence is noting but Fibonacci Number expression. We can find n’th Fibonacci number in O(Log n) time, see below for all method to find n’th Fibonacci Number.

Different methods for n’th Fibonacci Number.

Read full article from Count number of ways to fill a "n x 4" grid using "1 x 4" tiles - GeeksforGeeks