Cheapest Descent
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
1 <= rows, cols <= 10-100 <= costs[r][c] <= 100- Every row of
costshas the same length
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Cheapest Pool PassesMedium
- Coins From Either EndMedium
- Count DerangementsMedium
- Count the Free PlotsMedium
- Dice Sum WaysMedium
- Fairest Stone SplitMedium
- Fewest Perfect SquaresMedium
- Gems That ClashMedium