Maximum Ribbon Cut

Maximum Ribbon Cut asks: given a ribbon of length n and a fixed catalog of allowed piece lengths (each length reusable any number of times), split the ribbon so the count of pieces is maximized — it works because the best way to make length i is built from the best way to make some smaller length i - len plus one more cut of size len, so the optimal count for every length is assembled bottom-up from optimal counts for smaller lengths.

Recognize the pattern

• A single target quantity (n) must be built from a small, reusable, unlimited set of building blocks — this is unbounded knapsack (unlimited supply of each item).
• The objective is a count-of-items extremum (max or min pieces), not reachability or sum-of-values — that points to a 1D DP array indexed by remaining length.
• Order of pieces in the final cut doesn't matter, only the multiset — a signal this is coin-change-family, not a sequence/permutation problem.

Brute force → optimal

Brute force: recursively try every allowed length at every remaining amount — for remaining length r, try each len in the catalog, recurse on r-len, take max+1. Without memoization the same remaining lengths are recomputed repeatedly through different cut orders. Time, derived from the recursion tree: at each node you branch into up to m calls, but you can only keep recursing while the remaining amount is still ≥ the smallest catalog length — so recursion depth is bounded by n / min(lengths), not by n. Worst case is therefore O(m^(n / min_len)), not the looser O(m^n) you get by (wrongly) assuming depth n. For the catalog {3, 5, 7} used in the next section with n = 13: min_len = 3, so depth ≈ 13/3 ≈ 4, giving roughly O(3^4) = 81 leaf calls — orders of magnitude smaller than a naive O(3^13) ≈ 1.6 million. Space: O(n / min_len) recursion depth.

Optimal: the recursion's result depends only on the value r, so cache it. Bottom-up: build a table dp[0..n] where dp[i] = max pieces to exactly fill length i, computed in increasing order of i so every dependency dp[i-len] is already known.

Complexity, derived

The table has n+1 cells (i = 0..n). Filling cell dp[i] requires trying each of the m catalog lengths once (O(1) work per try: an array lookup, an add, a max). Total operations = (n+1) × m → time O(n·m). The table itself is the only extra storage → space O(n) (O(n) more if you reconstruct the actual pieces via a parent-choice array).

Traced example

n = 13, lengths = {3, 5, 7}. dp[i] = -∞ means length i is unreachable.

dp[13] is reached via dp[10]+1 (len 3), dp[8]+1 (len 5), or dp[6]+1 (len 7) — all give 3. Tracing dp[6]=2 back: dp[6] came from dp[3]+1 (len 3), and dp[3]=1 came from dp[0]+1 (len 3). So one optimal cut is {3, 3, 7} → 3 pieces, matching the expected output.

public int maxPieces(int n, int[] lengths) {
    int NEG = Integer.MIN_VALUE / 2; // avoid overflow on +1
    int[] dp = new int[n + 1];
    java.util.Arrays.fill(dp, NEG);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int len : lengths) {
            if (len > 0 && len <= i && dp[i - len] != NEG) {
                dp[i] = Math.max(dp[i], dp[i - len] + 1);
            }
        }
    }
    return dp[n] < 0 ? -1 : dp[n];
}

Pitfalls

• Confusing with minimum-coins: the recurrence looks identical to "fewest coins to make change" but there you take Math.min; flipping the comparator without also fixing the unreachable-sentinel (must be -∞, not +∞) silently breaks the max case.
• Sentinel overflow: using Integer.MIN_VALUE directly and then adding 1 overflows to a large positive number, making an unreachable cell look reachable and best. Use a safely-offset sentinel like MIN_VALUE/2.
• 0-length catalog entries corrupt bottom-up DP too, not just naive recursion: processing i in fixed increasing order does not make bottom-up DP immune — a len of 0 lets the inner loop read and rewrite dp[i] within the same i-pass. Trace lengths = [3, 0] at i = 3: the loop first tries len = 3 and sets dp[3] = dp[0] + 1 = 1; it then tries len = 0 and computes dp[3 - 0] = dp[3], which is the value just written earlier in this same pass (1), giving dp[3] = max(1, 1 + 1) = 2 — a fabricated extra piece from a zero-length cut. The fix is an explicit len > 0 guard (shown in the code above), not reliance on loop order.
• Off-by-one on dp array size: must allocate n+1 cells (index 0..n inclusive) — a common index-out-of-bounds source.

When to use / when not

Use bottom-up unbounded-knapsack DP when n is reasonably small (up to ~10^5–10^6) and the catalog is small — O(n·m) is cheap and the code is a simple double loop. Trade-off vs top-down memoized recursion: recursion is easier to derive from the brute force directly and only computes cells actually needed (useful if n is huge but reachable cells are sparse), at the cost of call-stack overhead and risk of stack overflow for large n; bottom-up avoids recursion overhead and stack limits but always computes the full table. Do not use this DP if n is astronomically large (e.g. 10^18) — then only a number-theoretic argument (valid solely when the catalog has special structure) can help; no greedy rule is safe in general.

Two naive greedy heuristics can seem tempting for maximizing piece count, and both fail. Largest-fitting-first ("always cut the biggest length that still fits") can dead-end instead of maximizing anything: n = 7, catalog {2, 3} → remaining 7, take 3 (largest fitting) → remaining 4, take 3 again (3 ≤ 4, still the largest fitting) → remaining 1, stuck — no catalog length ≤ 1. Followed exactly, the rule produces no valid decomposition at all, even though 2+2+3 = 7 (3 pieces) exists. Smallest-fitting-first is the more natural-looking greedy for a maximize-count objective (more small pieces should mean more pieces), but is equally unsafe: n = 8, catalog {3, 4} → remaining 8, take 3 (smallest fitting) → remaining 5, take 3 again → remaining 2, stuck — no catalog length ≤ 2 — even though 4+4 = 8 (2 pieces) is the only valid decomposition, and DP finds it immediately. Neither greedy direction is safe; only exploring all cut choices (what the DP recurrence does implicitly) guarantees the optimum.

Takeaways

• Maximum Ribbon Cut is unbounded knapsack optimizing piece count; swap the comparator to Math.min for the classic minimum-coins variant.
• dp[i] = max over usable lengths of dp[i-len]+1, with dp[0]=0 and unreachable cells sentineled to -∞.
• Brute-force recursion depth is bounded by n / min(lengths), not n — worst-case time is O(m^(n/min_len)), far smaller than a naive O(m^n) bound; the optimal bottom-up table is O(n·m) time / O(n) space.
• A len ≤ 0 guard is required in the DP loop regardless of iteration order — bottom-up order alone does not stop a 0-length entry from corrupting the current cell mid-pass.
• Neither largest-first nor smallest-first greedy is safe for maximizing piece count — both can dead-end, e.g. {2,3} at n=7 or {3,4} at n=8; only DP guarantees the optimum.

Recall: Why must the unreachable sentinel be -infinity (not 0 or +infinity) in the maximize-pieces version, and what breaks if you use +infinity instead?

Derived from the classic unbounded-knapsack / rod-cutting family of DP problems (cf. CLRS rod cutting, educative.io Grokking the DP Patterns).