Cheapest Walk to the Corner
Easy2-D Dynamic ProgrammingFree
Problem
A hiker crosses a rectangular map grid, where grid[r][c] is the effort (a non-negative integer) needed to cross cell (r, c). She starts at the top-left cell and must finish at the bottom-right cell, moving only right or down.
The cost of a walk is the sum of the efforts of every cell it visits, including the first and the last. Return the minimum possible cost.
Example 1
- Input:
- grid = [[1, 4, 2], [3, 1, 5], [6, 2, 1]]
- Output:
- 8
1 → 3 → 1 → 2 → 1 (down, right, down, right) costs 8; no other walk is cheaper.
Example 2
- Input:
- grid = [[5, 2, 8, 1]]
- Output:
- 16
With a single row there is only one walk: 5 + 2 + 8 + 1.
Constraints
- 1 ≤ grid.length, grid[0].length ≤ 200
- 0 ≤ grid[r][c] ≤ 100
Hint
Show the first hint
Think about the cheapest way to reach each cell, not just the corner.
Walkthrough
How to approach it
01Clarify before coding
- Can efforts be negative? No, they are between 0 and 100. (DP would still work with negatives here because moves only go right/down, so there are no cycles.)
- Do the start and end cells count? Yes, both are included in the sum.
- Can the grid be a single row or column? Yes; then there is exactly one walk.
02Brute force
Enumerate every right/down walk recursively and keep the smallest sum.
Cost: There are C(m + n - 2, m - 1) walks, astronomically many for 200 × 200; exponential time.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.