What is the brute force approach and complexity for Minimum Path Sum?

The cheapest total into a cell is its cost plus the cheaper of the cells above and to the left with time complexity O(2^(M + N)) and space complexity O(M + N).

What is the optimal approach and complexity for Minimum Path Sum?

row[c] = grid[r][c] + min(row[c] above, row[c − 1] to the left), updated in place with optimal time complexity O(M · N) and space complexity O(N).

How do you identify the pattern for Minimum Path Sum?

Look for key signals in the prompt: "minimizes the sum" indicates The goal is a minimum, not a count. Each cell keeps the smallest total of a path that reaches it.; "only down or right" indicates The same two feeders as Unique Paths: the cell above and the cell to the left.; "non-negative numbers on the cells" indicates Every cell adds its own cost once, on top of the cheaper of its two feeders..

Minimum Path Sum

Medium·LeetCode #64 Pro OnlySlight Variation

LeetCode

Problem Statement

Every cell of an m × n grid holds a cost (a number that is never negative). Start at the top-left cell and walk to the bottom-right cell, moving only down or right. Every cell on the path adds its cost to the total, including the start and the end.

Return the smallest total that any path can reach.

Input

grid, an m × n grid of non-negative numbers.

Output

The smallest sum of the costs along a path from the top-left cell to the bottom-right cell.

Example 1

Input: grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]

Output: 7

The path 1 → 3 → 1 → 1 → 1 (Right, Right, Down, Down) adds up to 7. No other path is cheaper.

Example 2

Input: grid = [[1, 2, 3], [4, 5, 6]]

Output: 12

There are three paths. The cheapest is 1 → 2 → 3 → 6 (Right, Right, Down), which adds up to 12.

Constraints

• 1 ≤ m, n ≤ 200
• 0 ≤ grid[i][j] ≤ 200

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“minimizes the sum”

→ The goal is a minimum, not a count. Each cell keeps the smallest total of a path that reaches it.

“only down or right”

→ The same two feeders as Unique Paths: the cell above and the cell to the left.

“non-negative numbers on the cells”

→ Every cell adds its own cost once, on top of the cheaper of its two feeders.

Approach Complexity Ladder

Brute Force — recurse back from the corner, take the cheaper way inO(2^(M + N))O(M + N)

The cheapest total into a cell is its cost plus the cheaper of the cells above and to the left

Better — a table of cheapest totalsO(M · N)O(M · N)

dp[r][c] = grid[r][c] + min(dp above, dp left), filled one cell at a time

Optimal — one row of cheapest totalsO(M · N)O(N)

row[c] = grid[r][c] + min(row[c] above, row[c − 1] to the left), updated in place

Brute Force Intuition

Let cost(r, c) be the cheapest total of a path from the top-left to (r, c), including (r, c). The path must enter (r, c) from above or from the left, so cost(r, c) = grid[r][c] + min(cost(r−1, c), cost(r, c−1)). The start costs only its own value.

Recognition rule for this sub-pattern:

dp[r][c] = dp[r−1][c] + dp[r][c−1] (ways) or min(…) + cost (cost).

Remember this · DP — Grid

Trigger

Move only right/down, count paths, minimum path cost, largest square of 1s.

Think

To reach cell (r, c), which cells could I have come from?

Key question

What does dp[r][c] mean, and what are the first row/column?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Grid translate into production architectures and low-level memory mechanics.

LLD Architecture