FunctionRacerProblemsRace

Lowest Photo Wall

MediumDynamic programmingPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems