Dynamic Programming Solution to Floor Tilling Problem

"""
Anthony Theocharis' Example Solution to Floor Tiling
"""

import numpy

class Floor(object):
    def __init__(self, width, height):
        self.width = int(width)
        self.height = int(height)

class TileSize(object):
    def __init__(self, width, height):
        self.width = int(width)
        self.height = int(height)

def can_be_tiled(floor, tile_sizes):
    """
    Given a floor of a size (N, M) [width, height] and a list of tile sizes,
    each with a unique width/height, determine if it is possible to cover the
    entire floor using some inter number of each type of tile.

    This implementation assumes that the tiles can be rotated.

    Approach:
        M = floor.height
        N = floor.width
        Any section is tileable if it can be broken into two subsections that
        are themselves tileable. For each subsection size (i,j) determine if it
        is tileable by finding two subsections that are tileable. Store the
        results in the array R, and build R up from (0, 0) to (N, M).
        A classic bottom-up dynamic programming / divide and conquer approach.

    Complexity:
        O(N * M) memory
        O(N * M * max(N, M)) steps
    """

    # Store a byte-array representing the tile-ability of all sub-section sizes
    # (really just needs to be a bit array, but that's hard in python)
    R = numpy.zeros((floor.width+1, floor.height+1), dtype=numpy.int8)

    # Any section with width=0 or height=0 is already 'tiled'
    R[:,0] = 1
    R[0,:] = 1

    # Any section that is identical to a single tile is tileable by definition
    for t in tile_sizes:
        if t.width <= floor.width and t.height <= floor.height:
            R[t.width][t.height] = 1

        if t.height <= floor.width and t.width <= floor.height:
            R[t.height][t.width] = 1

    # Syntax Note:
    # "for X in range(Y, Z+1):" is equivalent to
    # "for (int X=Y; X<=Z; X++)" in C style languates.

    # For each size of floor (i, j), determine if it's tileable.
    for i in range(1, floor.width+1):
        for j in range(1, floor.height+1):

            # Try to find a horizontal split such that each section is tileable
            if R[i][j] == 0:
                for a in range(0, (i/2)+1):
                    if R[a][j] == R[i-a][j] == 1:
                        R[i][j] = 1
                        break

            # Try to find a vertical split such that each section is tileable
            if R[i][j] == 0:
                for a in range(0, (j/2)+1):
                    if R[i][a] == R[i][j-a] == 1:
                        R[i][j] = 1
                        break

            # Mark the rotation of this section as tileable, if appropriate
            if R[i][j] == 1 and i <= floor.height and j <= floor.width:
                R[j][i] = 1

    if R[floor.width][floor.height] == 1:
        return 'yes'
    else:
        return 'no'

if __name__ == '__main__':
    print can_be_tiled(
        Floor(5, 7),
        [
            TileSize(2, 3),
            TileSize(3, 3),
            TileSize(2, 4),
            TileSize(5, 5),
        ]
    )