Introduction

This question is ambiguous unless you define the allowed moves or selection rules. A very common interpretation is the classic minimum path sum problem: start at the top-left cell, move only right or down, and find the path whose total sum is as small as possible. Under that interpretation, dynamic programming is the standard solution.

Define the Minimum Path Sum Recurrence

If grid[row][col] is the value in a cell, then the cheapest way to reach that cell is the cell value plus the cheaper of the two possible predecessor paths:

• from above
• from the left

That gives the recurrence:

dp[row][col] = grid[row][col] + min(dp[row - 1][col], dp[row][col - 1])

The top row and left column are special because they only have one valid predecessor direction.

This works because every path to a cell must end by arriving from one of those two positions. Once you know the best cost to the neighbors, the best cost to the current cell is immediate.

Implement It with Dynamic Programming

Here is a straightforward Python implementation:

1def min_path_sum(grid):
2    rows = len(grid)
3    cols = len(grid[0])
4
5    dp = [[0] * cols for _ in range(rows)]
6    dp[0][0] = grid[0][0]
7
8    for col in range(1, cols):
9        dp[0][col] = dp[0][col - 1] + grid[0][col]
10
11    for row in range(1, rows):
12        dp[row][0] = dp[row - 1][0] + grid[row][0]
13
14    for row in range(1, rows):
15        for col in range(1, cols):
16            dp[row][col] = grid[row][col] + min(dp[row - 1][col], dp[row][col - 1])
17
18    return dp[rows - 1][cols - 1]
19
20
21matrix = [
22    [1, 3, 1],
23    [1, 5, 1],
24    [4, 2, 1],
25]
26
27print(min_path_sum(matrix))

This returns 7, corresponding to the path 1 -> 3 -> 1 -> 1 -> 1.

The time complexity is O(rows * cols) because each cell is computed once. The space complexity is also O(rows * cols) in this version.

Reduce Space When You Only Need the Total

If you only care about the final minimum sum and not the full path reconstruction, you can compress the dynamic-programming table into one row.

1def min_path_sum_compact(grid):
2    rows = len(grid)
3    cols = len(grid[0])
4
5    dp = [0] * cols
6    dp[0] = grid[0][0]
7
8    for col in range(1, cols):
9        dp[col] = dp[col - 1] + grid[0][col]
10
11    for row in range(1, rows):
12        dp[0] += grid[row][0]
13        for col in range(1, cols):
14            dp[col] = grid[row][col] + min(dp[col], dp[col - 1])
15
16    return dp[-1]

This keeps the same time complexity but reduces space to O(cols).

Make Sure the Problem Interpretation Matches

The title could also describe other optimization problems, such as:

• choosing one number from each row
• selecting one number from each column
• minimizing a path with different movement rules

Those are different problems and may need different algorithms. So before coding, define the exact constraints. Dynamic programming is correct for the right-and-down path version, but not automatically for every matrix minimization question.

Common Pitfalls

The most common mistake is optimizing the wrong problem because the constraints were never stated clearly. A matrix path problem and a row-selection problem are not interchangeable.

Another issue is forgetting to initialize the first row and first column correctly. Those boundary cells have only one path into them, so they cannot use the full min recurrence yet.

People also sometimes use recursion without memoization, which works on tiny inputs but becomes much slower than the standard dynamic-programming table.

Summary

• A common interpretation of this question is the minimum path sum problem in a grid.
• For right-and-down movement, dynamic programming gives a clean optimal solution.
• The standard recurrence adds the current cell to the cheaper of the top or left path.
• The full-table solution is easy to read, and a one-row version reduces memory usage.
• Always define the exact matrix constraint first, because different interpretations require different algorithms.