Count the number of ways to tile the floor of size n x m using 1 x m size tiles | function to count the total number of ways ; table to store values of subproblems ; Fill the table upto value n ; recurrence relation ; base cases ; i = = m ; required number of ways ; Driver code
def countWays ( n , m ) : NEW_LINE INDENT count = [ ] NEW_LINE for i in range ( n + 2 ) : NEW_LINE INDENT count . append ( 0 ) NEW_LINE DEDENT count [ 0 ] = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( i > m ) : NEW_LINE INDENT count [ i ] = count [ i - 1 ] + count [ i - m ] NEW_LINE DEDENT elif ( i < m or i == 1 ) : NEW_LINE INDENT count [ i ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT count [ i ] = 2 NEW_LINE DEDENT DEDENT return count [ n ] NEW_LINE DEDENT n = 7 NEW_LINE m = 4 NEW_LINE print ( " Number ▁ of ▁ ways ▁ = ▁ " , countWays ( n , m ) ) NEW_LINE