Problem

Given a number n, count the number of ways to fill an n x 4 grid using 1 x 4 tiles. Tiles can be placed either horizontally or vertically, and each tile must cover exactly four cells.

Examples

Example 1

1
2
3

Input: n = 1
Output: 1
Explanation: Only one way, place the tile horizontally.

Example 2

1
2
3

Input: n = 2
Output: 1
Explanation: Only one way, place both tiles horizontally.

Example 3

1
2
3
4
5

Input: n = 4
Output: 2
Explanation: 
1. Place all tiles horizontally.
2. Place all tiles vertically.

Example 4

1
2
3
4
5
6

Input: n = 5
Output: 3
Explanation: 
1. Place all 5 tiles horizontally.
2. Place first 4 vertically and 1 horizontally.
3. Place first 1 horizontally and 4 vertically.

Solution

Method - Bottom up DP

Reasoning / Intuition

For each position in the grid, you can either:

  • Place a tile horizontally, which reduces the problem to filling an (n-1) x 4 grid.
  • Place a tile vertically, which requires 4 consecutive rows, reducing the problem to filling an (n-4) x 4 grid.

So, suppose we have 5x4 grid, $$ grid = \begin{array}{|c|c|c|c|} \hline & & & \\ \hline & & & \\ \hline & & & \\ \hline & & & \\ \hline & & & \\ \hline \end{array} \text{, tile = } \begin{array}{|c|c|c|c|} \hline \colorbox{green} & \colorbox{green} & \colorbox{green}& \colorbox{green} \\ \hline \end{array} $$

then, when the tile is placed horizontally: $$ grid = \begin{array}{|c|c|c|c|} \hline \colorbox{green} & \colorbox{green} & \colorbox{green} & \colorbox{green} \\ \hline & & & \\ \hline & & & \\ \hline & & & \\ \hline & & & \\ \hline \end{array} $$

and when it is placed vertically: $$ grid = \begin{array}{|c|c|c|c|} \hline \colorbox{green} & & & \\ \hline \colorbox{green} & & & \\ \hline \colorbox{green} & & & \\ \hline \colorbox{green} & & & \\ \hline & & & \\ \hline \end{array} $$

Now, let count(n) be the number of ways to place tiles on nx4 grid, then the recurrence is:

  • count(n) = count(n-1) + count(n-4)
  • Base cases: count(1) = count(2) = count(3) = 1, count(4) = 2

Approach

Use dynamic programming to build up the solution from the base cases, storing the number of ways for each grid size up to n.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
  int countWays(int n) {
    if (n <= 3) return 1;
    std::vector<int> dp(n + 1, 0);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
      if (i <= 3) dp[i] = 1;
      else if (i == 4) dp[i] = 2;
      else dp[i] = dp[i - 1] + dp[i - 4];
    }
    return dp[n];
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
  public int countWays(int n) {
    if (n <= 3) return 1;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
      if (i <= 3) dp[i] = 1;
      else if (i == 4) dp[i] = 2;
      else dp[i] = dp[i - 1] + dp[i - 4];
    }
    return dp[n];
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
  def countWays(self, n: int) -> int:
    if n <= 3:
      return 1
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
      if i <= 3:
        dp[i] = 1
      elif i == 4:
        dp[i] = 2
      else:
        dp[i] = dp[i - 1] + dp[i - 4]
    return dp[n]