The problem of tiling a grid plane with non-overlapping rectangles (2D rectangle tiling problem) is NP-complete (Danièle Beauquier et al., 1995). Currently, polynomial-time algorithms can only find approximate solutions that cover the largest possible area. In this research, the proposed stair algorithm significantly reduces the number of states recorded in dynamic programming, thereby improving the time complexity of finding exact solutions. The correctness of the algorithm has also been successfully proven. This algorithm can be applied to areas such as load balancing in parallel computing and integrated circuit design. Furthermore, an interactive demonstration was created to clearly present the functionality of the algorithm. Using the stair algorithm, this research successfully tested, compared, and analyzed the 7/3-approximation algorithm (Krzysztof Lorys and Katarzyna E. Paluch, 2000) and the 11/5-approximation algorithm (Piotr Berman et al., 2001) for the RTILE problem.