Lowest Photo Wall
Photos hang on a wall in rows, in the given order: photo i is widths[i] wide and heights[i] tall. Each row holds a run of consecutive photos whose widths add up to at most wall, and a row is as tall as its tallest photo. Rows are stacked one above another.
Return the smallest possible total height of all the rows. With no photos, return 0.
Example 1
widths [1,1,1,1]
heights [1,9,9,1]
wall 2
returns 11
Put the two tall photos together in the middle row: 1 + 9 + 1 = 11. Filling each row from the left gives 9 + 9 = 18.
Example 2
widths [3,2,2]
heights [4,4,2]
wall 5
returns 6
Rows 3, 2 and 2 are 4 and 2 tall. Pairing the two 2-wide photos instead makes both rows 4 tall.
Constraints
0 <= len(widths) <= 100len(heights) == len(widths)1 <= widths[i] <= wall <= 10001 <= heights[i] <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Lucky Toll TripsMedium
- No Double LeapsMedium
- One Forgiven DayMedium
- Paint the FenceMedium
- Shared Subsequence LengthMedium
- Trading With Rest DaysMedium
- Unique Binary Search TreesMedium
- Unique Grid PathsMedium