InternDoor

The cheapest walk across a grid

Mediumdynamic programming · grid

Reported in interviews at (where)

grid has m rows and n columns, and grid[i][j] is the cost of passing through that cell.

Start in the top-left cell and finish in the bottom-right one, moving only one cell right or one cell down at a time. Return the smallest total cost of the cells on your way, counting the first and the last cell.

Example 1
Input
grid = [[1,4,2],[3,2,6],[5,1,1]]
Output
8

Down, right, down, right: 1 + 3 + 2 + 1 + 1.

Example 2
Input
grid = [[5,0,9]]
Output
14

With one row the only way is straight across.

Limits

  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 1000

Hints

Hint 1

The cheapest way into a cell comes either from above or from the left, whichever is cheaper.

Hint 2

Fill the costs row by row; one row of them is all you need to keep.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.