Given an integer n, count the number of ways to tile a 2 x n board using dominoes and trominoes. Pattern focus: Profile DP. Build the board column by column and keep track of partial boundary states.
n = board length
number of valid tilings
Example 1:
Input:
n = 1
Output:
1
Explanation:
There is exactly one way to tile a 2 x 1 board.
Example 2:
Input:
n = 3
Output:
5
Explanation:
A standard small example for domino and tromino tiling.
Example 3:
Input:
n = 5
Output:
24
Explanation:
The recurrence grows quickly; the value at n=5 is 24.