Minimum Cost to Cut a Board into Squares

In this blog, we'll explore the problem of finding the minimum cost to cut a rectangular board into squares. This is an interesting problem that combines concepts from dynamic programming and geometric thinking. We'll break down the problem, look at different approaches to solve it, and understand the underlying principles.

Table of Contents#

  1. Problem Statement
  2. Approach - Dynamic Programming
    • Idea
    • Recurrence Relation
    • Memoization
    • Bottom - Up Implementation
  3. Example Usage
  4. Best Practices
    • Optimizing Space
    • Pre - processing Inputs
  5. Common Practices
    • Testing with Small Inputs
    • Analyzing Time and Space Complexity
  6. References

1. Problem Statement#

Given a rectangular board of size m x n, we want to cut it into squares. Each cut along a line (either horizontal or vertical) has a certain cost. The cost of a cut depends on the length of the line being cut. For example, if we have a horizontal cut at a distance y from the top of the board of length n, the cost of that cut is n * cost_y (where cost_y is the cost per unit length for that particular horizontal cut). Similarly for vertical cuts. Our goal is to find the minimum total cost to cut the board into squares.

2. Approach - Dynamic Programming#

Idea#

The key idea is to use dynamic programming. We can think of the problem as dividing the board into smaller sub - boards and computing the cost for each sub - board. Let dp[i][j] represent the minimum cost to cut a sub - board of size i x j into squares.

Recurrence Relation#

For a sub - board of size i x j starting at position (row_start, col_start):

  • We can make a horizontal cut at some position k (where 1 <= k < i). The absolute position of this cut in the original board is row_start + k. The cost of this cut is j * horizontalCuts[row_start + k]. Then we have two sub - boards: k x j (starting at (row_start, col_start)) and (i - k) x j (starting at (row_start + k, col_start)). The total cost for this option is j * horizontalCuts[row_start + k] + dp[k][j][row_start][col_start] + dp[i - k][j][row_start + k][col_start].
  • Similarly, we can make a vertical cut at some position l (where 1 <= l < j). The absolute position is col_start + l. The cost of this cut is i * verticalCuts[col_start + l]. Then we have two sub - boards: i x l (starting at (row_start, col_start)) and i x (j - l) (starting at (row_start, col_start + l)). The total cost for this option is i * verticalCuts[col_start + l] + dp[i][l][row_start][col_start] + dp[i][j - l][row_start][col_start + l].

The recurrence relation is: dp[i][j][row_start][col_start] = min(min_horizontal_cuts, min_vertical_cuts)

Memoization#

We can use memoization (top - down approach) to avoid recomputing the same sub - problems. We create a memo table (a 3D or 4D array or hash map) where we store the results of already computed dp[i][j][row_start][col_start] values. The key insight is that when we make a cut at relative position k within a sub-board starting at (row_start, col_start), the absolute position of that cut is row_start + k, so we must index into horizontalCuts and verticalCuts using these absolute positions.

def minCost(m, n, horizontalCuts, verticalCuts):
    memo = {}
    def dp(i, j, row_start, col_start):
        if (i, j, row_start, col_start) in memo:
            return memo[(i, j, row_start, col_start)]
        if i == 1 and j == 1:
            return 0
        min_cost = float('inf')
        # Horizontal cuts
        for k in range(1, i):
            cost = j * horizontalCuts[row_start + k] + dp(k, j, row_start, col_start) + dp(i - k, j, row_start + k, col_start)
            if cost < min_cost:
                min_cost = cost
        # Vertical cuts
        for l in range(1, j):
            cost = i * verticalCuts[col_start + l] + dp(i, l, row_start, col_start) + dp(i, j - l, row_start, col_start + l)
            if cost < min_cost:
                min_cost = cost
        memo[(i, j, row_start, col_start)] = min_cost
        return min_cost
    return dp(m, n, 0, 0)

Bottom - Up Implementation#

We can also implement it in a bottom - up way. We fill the dp table in increasing order of the size of the sub - boards. The key is to iterate over all possible sub-board positions, not just sizes. For a sub-board of size i x j starting at (row_start, col_start), when we make a cut at relative position k, we use horizontalCuts[row_start + k] to get the correct cost.

def minCostBottomUp(m, n, horizontalCuts, verticalCuts):
    dp = [[[[0]*(n + 1) for _ in range(m + 1)] for _ in range(n + 1)] for _ in range(m + 1)]
    for row_start in range(m - 1, -1, -1):
        for col_start in range(n - 1, -1, -1):
            for i in range(1, m - row_start + 1):
                for j in range(1, n - col_start + 1):
                    if i == 1 and j == 1:
                        continue
                    min_cost = float('inf')
                    # Horizontal cuts
                    for k in range(1, i):
                        cost = j * horizontalCuts[row_start + k] + dp[row_start][col_start][k][j] + dp[row_start + k][col_start][i - k][j]
                        if cost < min_cost:
                            min_cost = cost
                    # Vertical cuts
                    for l in range(1, j):
                        cost = i * verticalCuts[col_start + l] + dp[row_start][col_start][i][l] + dp[row_start][col_start + l][i][j - l]
                        if cost < min_cost:
                            min_cost = cost
                    dp[row_start][col_start][i][j] = min_cost
    return dp[0][0][m][n]

3. Example Usage#

Let's say we have a board of size 3 x 3. The horizontal cuts are at positions 1 and 2 from the top with costs [0, 1, 2] (where index k represents the cut at position k from the top). The vertical cuts are at positions 1 and 2 from the left with costs [0, 3, 4] (where index l represents the cut at position l from the left). Note that index 0 is a dummy value since cuts only occur at valid positions.

Using the bottom - up approach:

  • For sub-board starting at (0, 0) with size i = 2, j = 2:
    • Horizontal cut at relative position k = 1 (absolute position 0 + 1 = 1): cost is 2 * horizontalCuts[1] + dp[0][0][1][2] + dp[1][0][1][2].
      • For sub-board i = 1, j = 2 starting at (0, 0): no cuts needed, so dp[0][0][1][2] = 3 (computed as one vertical cut at absolute position 0 + 1 = 1).
      • For sub-board i = 1, j = 2 starting at (1, 0): same cost structure, dp[1][0][1][2] = 3.
      • So horizontal cut cost is 2 * 1 + 3 + 3 = 8.
    • Vertical cut at relative position l = 1 (absolute position 0 + 1 = 1): cost is 2 * verticalCuts[1] + dp[0][0][2][1] + dp[0][1][2][1].
      • For sub-board i = 2, j = 1 starting at (0, 0): horizontal cut at relative position k = 1 gives cost 1 * horizontalCuts[1] = 1. So dp[0][0][2][1] = 1.
      • For sub-board i = 2, j = 1 starting at (0, 1): cut at absolute position 1, so cost 1 * horizontalCuts[1] = 1. So dp[0][1][2][1] = 1.
      • So vertical cut cost is 2 * 3 + 1 + 1 = 8.
    • dp[0][0][2][2] = min(8, 8) = 8.
  • Similar calculations apply for other sub-boards, eventually yielding the minimum cost for the full 3 x 3 board at dp[0][0][3][3].

4. Best Practices#

Optimizing Space#

In the bottom - up approach, we can optimize space. Since when computing dp[i][j], we only need the values of dp[i - k][j] (for horizontal cuts) and dp[i][j - l] (for vertical cuts), we can use a 1D array instead of a 2D array for some cases (if the order of filling the table allows it).

Pre - processing Inputs#

Sort the horizontal and vertical cut positions (if not already sorted) and calculate the effective cut costs. For example, if we have horizontal cut positions h1 < h2 <...< h_m-1, the effective cost for a cut between h_i and h_{i + 1} can be pre - computed.

5. Common Practices#

Testing with Small Inputs#

Always test your code with small inputs (like 1x1, 2x2 boards) to ensure that the base cases and the recurrence relation are working correctly.

Analyzing Time and Space Complexity#

  • Time Complexity (Top - Down with Memoization): In the worst case, for a board of size m x n, the number of sub - problems is O(mn). For each sub - problem, in the worst case, we make O(m + n) cuts. So the time complexity is O(mn(m + n)).
  • Space Complexity (Top - Down with Memoization): The space complexity is dominated by the memo table, which is O(mn).
  • Time Complexity (Bottom - Up): Also O(mn(m + n)) as we fill the O(mn) table and for each cell, we make O(m + n) operations.
  • Space Complexity (Bottom - Up): O(mn) for the dp table.

6. References#

This blog has provided a comprehensive overview of the minimum cost to cut a board into squares problem. By understanding the dynamic programming approach, best practices, and common testing methods, you can effectively solve this and similar problems.

2026-07