309. Maximize The Cut Segments

Given a rod of length n and three allowed cut lengths x, y, and z (each usable any number of times, in any order), find the maximum number of pieces the rod can be cut into using only cuts of those three lengths so that the pieces exactly account for the whole rod. Print 0 if it's not possible to cut the rod exactly using only those lengths.

Input: The first line contains an integer n, the rod length. The second line contains three space-separated integers x, y, z, the allowed cut lengths. Output: Print a single integer - the maximum number of pieces the rod can be cut into, or 0 if it can't be cut exactly using only x, y, and z.

1 <= n <= 10^4, 1 <= x, y, z <= n

Using a sentinel like NEGATIVE INFINITY (rather than 0) for 'unreachable' lengths is essential - if 0 were used instead, an unreachable length could be mistakenly treated as a valid (but poor) achievable segment count, propagating an incorrect result forward.

Cut a rod of length n into the maximum number of pieces using only three allowed cut lengths. Brute force: Try every possible combination and order of cuts summing to n directly - this branches combinatorially, when a single bottom-up DP directly computes the maximum segment count. Optimised: Since dp[i] only depends on THREE specific smaller sub-problems (i-x, i-y, i-z), building the table bottom-up computes each achievable length's maximum segment count exactly once, reused by every larger length that needs it.

Add a memo table indexed by remaining rod length so that once the best number of pieces for a given length has been computed, it is cached and reused instead of recomputed. The recursive structure stays identical to the brute-force version, but each distinct remaining length is now solved only once, collapsing the exponential blowup into one entry per length from 0 to n. Time: O(n) Space: O(n)

Build the same DP table iteratively from the smallest lengths upward instead of recursively from the top down: dp[0] = 0, and for each length i from 1 to n, dp[i] = 1 + max(dp[i-x], dp[i-y], dp[i-z]) over whichever of those are valid and reachable (marking i as unreachable otherwise). The final answer is dp[n] if reachable, else 0. This computes the exact same values as the memoized version but as a simple loop, avoiding recursive call overhead and any risk of deep recursion for n up to 10^4. Time: O(n) Space: O(n)

Recursively try every way to make the first cut: from a rod of length n, try cutting off a piece of length x (if n >= x), y (if n >= y), or z (if n >= z), and recurse on the remaining length in each case, taking the maximum number of pieces found across all branches plus one for the cut just made. This explores every valid sequence of cuts and is guaranteed correct, but without any memory of previously solved subproblems it re-solves the same remaining lengths over and over, causing exponential blowup. Time: O(3^(n / min(x,y,z))) Space: O(n / min(x,y,z))

1. dp[i] = maximum number of segments achievable for a rod of length exactly i, or unreachable if no combination of x,y,z sums to exactly i. 2. dp[i] = 1 + max(dp[i-x], dp[i-y], dp[i-z]) over whichever of those are reachable and non-negative; dp[0]=0. 3. The final answer is dp[n] if reachable, otherwise 0 - don't confuse an unreachable length with a valid answer of 0 pieces.

Time: O(n) - one pass building the dp table, with O(1) work per position (checking 3 fixed offsets). Space: O(n), for the dp array.

Test a length n that cannot be formed by any combination of x, y, z (expect 0, not confused with a reachable answer), x/y/z equal to each other or to n itself, and n at its upper bound of 10^4.

Be ready to explain the distinction between 'dp[i] is UNREACHABLE' (no combination of x,y,z sums to exactly i) versus 'dp[i]=0' (a genuinely valid answer of zero pieces, which only happens at i=0) - conflating these two states is a common source of incorrect final answers.