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

$ curl repovive.com/roadmaps/dynamic-programming/broken-profile-dp-plug-dp/tri-tiling-implementation

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

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

$ curl repovive.com/roadmaps/dynamic-programming/broken-profile-dp-plug-dp/tri-tiling-implementation

Repovive

Tri Tiling - Implementation - Broken Profile DP (Plug DP) | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

Tri Tiling - Implementation

Recurrence solution

Here's the solution handling multiple test cases:

function triTiling()
    while true
        n := read integer
        if n = -1 then
            break
        if n is odd then
            print 0
            continue
        if n = 0 then
            print 1
            continue
        a[0] := 1
        a[1] := 3
        for i from 2 to n/2
            a[i] := 4 * a[i-1] - a[i-2]
        print a[n/2]

Loop until $n = -1$ . Return $0$ for odd $n$ . Use recurrence $a[i] = 4a[i-1] - a[i-2]$ for even values.

Time complexity: $O(n \cdot 2^m)$ .

Space complexity: $O(2^m)$ in time and $O(n)$ in space.