Cut the dough: hints, no solution
Medium · 1-D dynamic programming
A bakery sells dough by the piece. A slab has length slab and can be cut into pieces, but only some piece lengths are on the price list: a piece of length lengths[i] sells for values[i]. Any listed length may be used as many times as you like. Pieces cannot overlap or run past the end of the slab, and leftover dough is thrown away for no value. Return the maximum total value you can obtain from one slab. If no listed piece fits, return 0.
Examples
- Input
- slab = 8, lengths = [3, 5, 4], values = [10, 17, 13]
- Output
- 27
- Note
- Cut one piece of 5 and one of 3 for 17 + 10. Two pieces of 4 give only 26.
- Input
- slab = 2, lengths = [3], values = [9]
- Output
- 0
- Note
- The only listed piece is longer than the slab.
- Input
- slab = 6, lengths = [4, 3], values = [7, 5]
- Output
- 10
- Note
- Two pieces of 3 beat one piece of 4 plus scrap.
Constraints
- 0 <= slab <= 20000
- 0 <= lengths.length <= 200, and values has the same length
- 1 <= lengths[i] <= 20000, 1 <= values[i] <= 1000
Hint 1: a nudge
If you knew the best value for every shorter slab, how would you work out the best value for this one? What is the last piece you might cut?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.