Minimum Path Sum

MediumDynamic Programminggrid DP

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a 2D integer matrix grid of size m x n, where each cell grid[i][j] holds a non-negative cost. Starting at the top-left cell grid[0][0], you want to reach the bottom-right cell grid[m-1][n-1]. At every step you may move only **one cell to the right** or **one cell down**. The cost of a path is the sum of the values of every cell it visits, including both the starting and ending cells. Return the **minimum possible total cost** among all valid paths from the top-left corner to the bottom-right corner.

Examples

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
The path 1 -> 3 -> 1 -> 1 -> 1 sums to 7, which is the smallest achievable total.
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
The path 1 -> 2 -> 3 -> 6 sums to 12; going down earlier costs more because of the 4 and 5.
Input: grid = [[5]]
Output: 5
A single cell means the start and end are the same, so the cost is just that cell's value.

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More grid DP problems