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

write program takes input width, w , height h of grid , outputs number of different ways tile w-by-h grid (2x1) dominoes

i know how solve problem 3 x n grid writing recursive formula hard me!

i have no idea how it!

i created 2 functions f(n) - complete way of tiling till n , s(n) number of ways of incomplete tiling 3 x n ! here height variable cannot think of anything

constraints : (0 ≤ w+h ≤ 22)

this sort of dpish under hood. idea ivlad's: backtracking 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) in range(max(m, n)) j in range(min(m, n))))   print(count_tilings(18, 4)) 

the trick here keeping number of states blowing up. first, choose leftmost topmost square cover, partial cover can described number of contiguous covered squares in leftmost-topmost order, followed #rows partially covered, total of @ (#rows * #columns + 1) * 2^#rows states. second, orient grid there @ least many columns rows, bounding latter number 10 interesting computations (because 11 11 trivial).