Maximize The Cut Segments

The problem, simply

You get a ribbon of length n and three allowed piece sizes x, y and z. You must cut the whole ribbon into pieces, and every piece must be exactly one of those sizes. No scrap may be left over.

Give back the largest number of pieces you can make. If there is no way to use up the ribbon exactly, give back 0.

A story to remember it

Picture it

The notebook is one row of boxes, one box per ribbon length from 0 to 7. Each box says the most pieces for that length, or x if that length cannot be cut exactly.

Examples

Way 1: the simple way

Try every first cut. Cut off a piece of size x, y or z, and ask the same question about the ribbon that is left.

1. If the ribbon has length 0, you are done: 0 more pieces.
2. If the length went below 0, that cut was not allowed. Say "impossible" with -1.
3. Otherwise try all three cuts, take the best answer that is not impossible, and add 1 for the piece you cut.

class Solution {
    public int maximizeCuts(int n, int x, int y, int z) {
        int best = solve(n, x, y, z);
        return best < 0 ? 0 : best;            // no exact way means 0
    }

    private int solve(int n, int x, int y, int z) {
        if (n == 0) return 0;                  // nothing left to cut
        if (n < 0) return -1;                  // cut too much, not allowed
        int best = Math.max(solve(n - x, x, y, z),
                   Math.max(solve(n - y, x, y, z), solve(n - z, x, y, z)));
        if (best < 0) return -1;               // every cut got stuck
        return best + 1;                       // count the piece we just cut
    }
}

How long it takes: every call splits into three more calls, and the tree can be about n levels deep, so O(3^n). Extra room: the waiting calls form a pile as tall as the ribbon, O(n).

Way 2: the clever way

The tree asks the same small questions again and again. So answer each length once, from short to long, and write it in the notebook.

1. Make a row dp of boxes for lengths 0 to n. Fill it with -1, which means "cannot be done". Set dp[0] = 0.
2. For each length i from 1 to n, try each cut c. If i - c is at least 0 and dp[i - c] is not -1, then dp[i - c] + 1 is a candidate.
3. Keep the biggest candidate in dp[i].
4. The answer is dp[n], or 0 if it is still -1.

The arrows show which shorter lengths each box looks back at.

import java.util.Arrays;

class Solution {
    public int maximizeCuts(int n, int x, int y, int z) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, -1);                   // -1 means this length cannot be cut exactly
        dp[0] = 0;
        int[] cuts = {x, y, z};
        for (int i = 1; i <= n; i++) {
            for (int c : cuts) {
                if (i >= c && dp[i - c] != -1) {
                    dp[i] = Math.max(dp[i], dp[i - c] + 1);   // cut one piece, look up the rest
                }
            }
        }
        return dp[n] == -1 ? 0 : dp[n];
    }
}

How long it takes: n boxes, three looks each, O(n). Extra room: one row of n + 1 boxes, O(n).

Watch out for

• The problem wants 0, not -1, when no exact cut exists. Convert at the very end.
• Two or three of the sizes can be equal. That is fine, the loop tries the same cut twice.
• Greedy does not work. Always taking the smallest piece fails for n = 5 with sizes 2, 3, 5: 2 + 2 leaves 1.

What interviewers ask next

• What if there are k allowed sizes instead of three? Loop over all of them. Time becomes O(n * k).
• What if you want the fewest pieces? Same notebook with min instead of max. That is the coin change problem.
• How many different ways can you cut it? Add up the counts instead of taking the best. Watch whether order matters.
• Can you write it top down? Yes. Keep the recursion and save each answer in a map or array the first time you compute it.

Remember this

Grown-up words: the notebook is the DP table, asking the same small question again is an overlapping subproblem, filling from short to long is bottom up dynamic programming, and the whole setup is an unbounded knapsack that maximizes the count.