"static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 17:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:Tfba,

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

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

Example 2

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

Example 3

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

Example 4

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

[{"language":"C++","code":"class Solution {\npublic:\n  int countWays(int n) {\n    if (n <= 3) return 1;\n    std::vector<int> dp(n + 1, 0);\n    dp[0] = 0;\n    for (int i = 1; i <= n; ++i) {\n      if (i <= 3) dp[i] = 1;\n      else if (i == 4) dp[i] = 2;\n      else dp[i] = dp[i - 1] + dp[i - 4];\

Related Tags