Dynamic Programming Approach for Solving Rectangle Partitioning Problem

Rectangle partitioning is one of the most common combinatorial problems which main purpose is to count possible configurations based on some given variables. Typical approach to solve this problem needs a polynomial time complexity, which leads to a new issue when time and memory is a crucial factor in this problem solving. One specific rectangular partitioning problem that has this issue is to count how many possible partitions can be done on a M×N rectangle to divide it into exactly two subregions. In this paper, we propose a novel solution for the aforementioned problem using dynamic programming with profile method, also known as broken profile DP. This broken profile DP method is famous for solving complex 2D grid problems by breaking it into some simpler subproblems and exploiting the special structure of the particular problem, which is referred as a profile. A disjoint-set data structure is used alongside with broken profile DP to validate each line configuration’s connectivity, since the DP transition is processed line-by-line. In the implementation later on, it is necessary to implement big integer in order to store very big values. Based on the case study testing result, the solution using broken profile dynamic programming method requires an average time of 0.0012 seconds and an average memory of 530 KiB.