Count number of ways to fill a " n ▁ x ▁ 4" grid using "1 ▁ x ▁ 4" tiles | Returns count of count of ways to place 1 x 4 tiles on n x 4 grid . ; Create a table to store results of subproblems dp [ i ] stores count of ways for i x 4 grid . ; Fill the table from d [ 1 ] to dp [ n ] ; Base cases ; dp ( i - 1 ) : Place first tile horizontally dp ( n - 4 ) : Place first tile vertically which means 3 more tiles have to be placed vertically . ; Driver code to test above
def count ( n ) : NEW_LINE INDENT dp = [ 0 for _ in range ( n + 1 ) ] NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if i <= 3 : NEW_LINE INDENT dp [ i ] = 1 NEW_LINE DEDENT elif i == 4 : NEW_LINE INDENT dp [ i ] = 2 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] = dp [ i - 1 ] + dp [ i - 4 ] NEW_LINE DEDENT DEDENT return dp [ n ] NEW_LINE DEDENT n = 5 NEW_LINE print ( " Count ▁ of ▁ ways ▁ is " ) , NEW_LINE print ( count ( n ) ) NEW_LINE