#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/broken-profile-dp-plug-dp/counting-tilings-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/broken-profile-dp-plug-dp/counting-tilings-implementation

Repovive

Counting Tilings - Implementation - Broken Profile DP (Plug DP) | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

Counting Tilings - Implementation

Full solution

Precompute transitions, then run DP:

function countTilings(n, m):
    MOD := 1000000007
    trans := array of size 2^n, each entry is empty list
    
    function fill:
        if row = n then trans[cur_mask].append(next_mask)
        return
        if cur_mask has bit row set then fill
        else fill
        if row + 1 < n and cur_mask bit (row+1) not set then fill
    
    for mask from 0 to 2^n - 1:
        fill(0, mask, 0)
    
    dp := 2D (two-dimensional) array (m+1) x 2^n, all zeros
    dp[0][0] := 1
    for c from 0 to m - 1:
        for cur_mask from 0 to 2^n - 1:
            Each next_mask in trans[cur_mask]:
                dp[c+1][next_mask] := mod MOD
    return dp[m][0]

Time: $O(m \cdot 2^n \cdot T)$ . Space: $O(2^n)$ for the profile states.