Number of ways to tile a W x H Grid with 2 x 1 and 1 x 2 dominos?

Write a program that takes as input the width, W and height H of the grid and outputs the number of different ways to tile a W-by-H grid with (2x1) dominoes

I know how to solve the problem with 3 x N grid but writing the recursive formula for this is too hard for me!

I have no idea how to do it!

I created two functions F(n) - The complete way of tiling till N and S(n) for number of ways of incomplete tiling for 3 x N ! But here as the height is variable I cannot think of anything

Constraints : (0 ≤ W+H ≤ 22)

This is sort of DPish under the hood. The idea is IVlad's: backtracking with memoization.

memo = {}


def count_tilings_recursive(uncovered):
    if len(uncovered) & 1:
        return 0
    if not uncovered:
        return 1
    if uncovered not in memo:
        i, j = min(uncovered)
        memo[uncovered] = count_tilings_recursive(uncovered - {(i, j), (i, j + 1)}) + count_tilings_recursive(uncovered - {(i, j), (i + 1, j)})
    return memo[uncovered]


def count_tilings(m, n):
    return count_tilings_recursive(frozenset((i, j) for i in range(max(m, n)) for j in range(min(m, n))))


print(count_tilings(18, 4))

The trick here is keeping the number of states from blowing up. First, we always choose the leftmost then topmost square to cover, so that the partial cover can be described as the number of contiguous covered squares in leftmost-topmost order, followed by #rows partially covered, for a total of at most (#rows * #columns + 1) * 2^#rows states. Second, we orient the grid so that there are at least as many columns as rows, bounding the latter number by 10 for interesting computations (because 11 by 11 is trivial).