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.<\/p>\n
For example, when N=3, the 2*3 rectangle can be filled in the following ways:<\/p>\n
Various cases are generated depending on how the tiles are arranged. Therefore, it is possible to recursively explore all combinations by finding appropriate rules.<\/p>\n
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.<\/p>\n
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).<\/p>\n
The following recurrence relation can be established:<\/p>\n
dp[n] = dp[n-1] + dp[n-2]<\/code><\/pre>\nWhen 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:<\/p>\n