FunctionRacerProblemsRace

Cheapest Descent

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

costs is a grid of entry costs. You may begin in any cell of the top row. From a cell in row r and column c you may move to row r + 1 in column c - 1, c or c + 1, as long as that column exists. You stop as soon as you have entered a cell of the bottom row. Return the smallest possible total of the costs of all the cells you entered, including the first and the last. Costs may be negative. A grid with one row costs just its cheapest cell.

Example 1

costs [[3,8,1],[9,4,2],[5,7,6]]
returns 9

Start at the 1, move straight down to the 2, then to the 6: 1 + 2 + 6 = 9.

Example 2

costs [[5,-3],[2,4]]
returns -1

Start at -3 and move down-left to the 2: -3 + 2 = -1.

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