JavaScript Coding Test Course, 2 N Tile Filling

Problem Definition

This is a problem of calculating the number of ways to fill a 2*N rectangle with tiles of size 1*2 or 2*1. In other words, for a given length N, we aim to find the number of ways to completely fill the rectangle using the tiles. This problem can be solved using the Dynamic Programming technique.

Problem Description

For example, when N=3, the 2*3 rectangle can be filled in the following ways:

  • 1->1->1
  • 1->2
  • 2->1
  • 2->2
  • 2->1->1

Various cases are generated depending on how the tiles are arranged. Therefore, it is possible to recursively explore all combinations by finding appropriate rules.

Problem Approach

1. Recursive Approach

The most basic method is to use recursion to explore all possible cases. However, this is inefficient and has a high time complexity, making it impractical.

2. Dynamic Programming

Using Dynamic Programming allows us to store previous computed results and utilize them to avoid redundant calculations. This approach reduces the time complexity to O(N).

Dynamic Programming Implementation

Recurrence Relation

The following recurrence relation can be established:

dp[n] = dp[n-1] + dp[n-2]

When filling the last column with a 1×2 tile, we consider the case of dp[n-1], and when filling with a 2×1 tile, we consider the case of dp[n-2]. The base conditions are as follows:

  • dp[1] = 1 (Filling with a 1*2 tile)
  • dp[2] = 2 (Filling with a 2*1 or 1*2 tile)

JavaScript Example Code


function tileWays(n) {
    if (n === 1) return 1;
    if (n === 2) return 2;

    let dp = new Array(n + 1);
    dp[1] = 1;
    dp[2] = 2;

    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

console.log(tileWays(3)); // Output: 3

Conclusion

The 2*N tile filling problem is a fundamental dynamic programming problem that is frequently featured in coding tests. Through this problem, we learn the importance of choosing efficient approaches when solving algorithmic problems.
It is essential to understand the basics of Dynamic Programming well and to develop the ability to solve complex problems step by step using it. I hope to become a better developer through practice on various problems.