Paper Cut into Minimum Number of Squares

Paper Cut into Minimum Number of Squares asks you to slice a rectangular sheet of paper into the fewest possible perfect squares. It looks like a simple greedy problem — and the greedy intuition is a great place to start — but the exact minimum needs dynamic programming.

The slow way first

The natural greedy move: repeatedly slice off the largest square that fits, whose side is the smaller of the two remaining dimensions, and count how many you take. For 5 x 3 that gives 3x3, then a 2x3 strip, then 2x2, then a 2x1 strip needing two 1x1 squares — total 4.

The trouble is that greedy is not always optimal. For a 5 x 6 sheet greedy takes 5, but the true minimum is 5... and there are larger sizes where greedy overshoots. So greedy is a fine warm-up and a sanity check, but to guarantee the minimum we have to try every cut.

The idea: try every cut and keep the best

Define dp(w, h) = the minimum number of squares for a w x h sheet. If w == h the sheet is already a square, so the answer is 1. Otherwise every solution is formed by one straight cut that splits the sheet into two sub-rectangles — either a vertical cut (into k x h and (w-k) x h) or a horizontal cut (into w x k and w x (h-k)). Recurse on both halves, add their answers, and take the minimum over all cut positions.

Memoizing dp(w, h) (with lru_cache) turns the exponential recursion into a polynomial DP over all w x h subproblems.

Walk through it

Step through the animation. First it shows the greedy slicing on the 5 x 3 grid: a 3x3 block, then 2x2, then two 1x1 cells — 4 squares. Then it resets and switches to the DP view, which tries every vertical and horizontal cut and confirms the exact minimum is 4.

Pseudocode

dp(w, h):
    if w == h:                       # already a perfect square
        return 1
    best = w * h                     # worst case: all 1x1 squares
    for k from 1 to w//2:            # every vertical cut
        best = min(best, dp(k, h) + dp(w - k, h))
    for k from 1 to h//2:            # every horizontal cut
        best = min(best, dp(w, k) + dp(w, h - k))
    return best

The Python solution

from functools import lru_cache
 
def min_squares(w, h):
    @lru_cache(maxsize=None)
    def dp(w, h):
        if w == h:
            return 1
        best = w * h
        # try every vertical cut
        for k in range(1, w // 2 + 1):
            best = min(best, dp(k, h) + dp(w - k, h))
        # try every horizontal cut
        for k in range(1, h // 2 + 1):
            best = min(best, dp(w, k) + dp(w, h - k))
        return best
    return dp(w, h)

• dp(w, h) returns the minimum squares for a w x h piece, memoized so each subproblem is solved once.
• if w == h is the base case — a square sheet is one piece.
• best = w * h seeds the answer with the worst case (cut everything into 1x1 squares).
• The first loop tries every vertical cut at column k, splitting into k x h and (w-k) x h. We only go up to w // 2 because cut k and cut w - k are mirror images.
• The second loop tries every horizontal cut at row k the same way.
• We keep the smallest total over all cuts, and lru_cache makes the overlapping subproblems cheap.

Complexity

There are O(n * m) distinct w x h subproblems, and each tries O(n + m) cut positions, so the exact DP is O(n * m * (n + m)) with O(n * m) cache space. Greedy is far faster but can miss the optimum.

When this pattern shows up

Practice