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
< ? php function countt ( $ n ) { $ dp [ $ n + 1 ] = 0 ; $ dp [ 0 ] = 0 ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) { if ( $ i >= 1 && $ i <= 3 ) $ dp [ $ i ] = 1 ; else if ( $ i == 4 ) $ dp [ $ i ] = 2 ; else $ dp [ $ i ] = $ dp [ $ i - 1 ] + $ dp [ $ i - 4 ] ; } return $ dp [ $ n ] ; } $ n = 5 ; echo " Count ▁ of ▁ ways ▁ is ▁ " , countt ( $ n ) ; ? >