Search⌘ K
AI Features
Home
Courses
Grokking Dynamic Programming Interview

Maximum Ribbon Cut

Explore how to solve the Maximum Ribbon Cut problem by understanding and applying the unbounded knapsack dynamic programming pattern. Learn to implement naive recursion and then improve it with top-down memoization and bottom-up tabulation to optimize time and space complexity. This lesson equips you with practical DP techniques to maximize ribbon pieces from given sizes effectively.

We'll cover the following...

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 1313 and possible sizes as [5,3,8][5, 3, 8]. The ribbon length can be obtained by cutting it into one piece of length 55 and another of length 88 (as 5+8=135 + 8 = 13), or, into one piece of length 33 and two pieces of length 55 (as 3+5+5=133 + 5 + 5 = 13). As we wish to maximize the number of pieces, we choose the second option, cutting the ribbon into 33 pieces.

Constraints:

  • 1≤1 \leq sizes.length ≤12\leq 12

  • 1≤1 \leq sizes[i] ≤231−1\leq 2^{31} -1

  • 0≤0 \leq n ≤1500\leq 1500 ...

No.

n

sizes

Count of Pieces

1

5

[1, 2, 3]

5

2

13

[5, 3, 8]

3

3

3

[5]

-1

Try it yourself

Implement your solution in the following playground:

Java
usercode > RibbonCut.java
import java.util.*;
public class RibbonCut{
    public static int countRibbonPieces(int n, int[] sizes)
    {
        // write your code here
        return -1;
    }
}
Maximum Ribbon Cut
...