Maximum Ribbon Cut
Let's solve the Maximum Ribbon Cut problem using Dynamic Programming.
Statement
Given a ribbon of length n
and a set of possible sizes
, cut the ribbon in sizes
such that n
is achieved with the maximum number of pieces.
You have to return the maximum number of pieces that can make up n
by using any combination of the available sizes
. If the n
can’t be made up, return 1
, and if n
is 0
, return 0
.
Let’s say, we have a ribbon of length $13$ and possible sizes as $[5, 3, 8]$. The ribbon length can be obtained by cutting it into one piece of length $5$ and another of length $8$ (as $5 + 8 = 13$), or, into one piece of length $3$ and two pieces of length $5$ (as $3 + 5 + 5 = 13$). As we wish to maximize the number of pieces, we choose the second option, cutting the ribbon into $3$ pieces.
Constraints:

$1 \leq$
sizes.length
$\leq 12$ 
$1 \leq$
sizes[i]
$\leq 2^{31} 1$ 
$0 \leq$
n
$\leq 1500$
Examples
Level up your interview prep. Join Educative to access 70+ handson prep courses.