Medium · DP
Minimum Path Sum
You cannot walk left or up, so when you arrive at a cell you must have come from above or from the left — two possible pasts, pick the cheaper. Fill the table row by row and the bottom-right corner holds the answer.
At a glance<code>best[i][j] = a[i][j] + min(best[i-1][j], best[i][j-1])</code>, with the first row and column accumulated — answer sits at <code>best[n][m]</code>.
Problem
Input: The first line has n and m (1 ≤ n, m ≤ 10). Then n lines of m integers (0 ≤ a ≤ 100), the grid.
Output: The minimum possible sum of cells on a path from the top-left cell to the bottom-right cell, moving only right or down.
Samples:
| Input | Output |
|---|---|
2 2 | 3 |
3 3 | 7 |
The classic 3×3 sample looks like the right path should dodge the 5 and the 4 — trace it: 1 → 1 → 5 is worse than 1 → 3 → 1 … the table exists precisely because eyes are bad at this and two mins per cell are not.
Your solution
Custom input for "Run my input"
Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.
Stuck? Hints
Hint 1 — Two pasts per cell
Because left and up moves are forbidden, the cheapest way to stand on (i, j) is the cheaper of the cheapest ways to (i−1, j) and (i, j−1), plus the toll a[i][j] itself. That is the whole recurrence: best[i][j] = a[i][j] + min(best[i-1][j], best[i][j-1]).
Hint 2 — Borders have only one past
In the first row you can only have come from the left; in the first column, only from above. So fill them by plain accumulation best[1][j] = best[1][j-1] + a[1][j] — a frequent bug is leaving border cells equal to the grid values instead of the running sum.
Hint 3 — Greedy is not enough — the table is
Tempting shortcut: at each cell step to the cheaper neighbour. It fails — a slightly expensive step can unlock a cheap corridor. The DP table never regrets, because it computes the true optimum for every cell before any of them is needed. When you feel the urge to decide locally, reach for a table instead.
Solution (try it first!)
#include <iostream>
using namespace std;
int best[12][12];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int a;
cin >> a;
if (i == 1 && j == 1) best[i][j] = a;
else if (i == 1) best[i][j] = best[i][j - 1] + a;
else if (j == 1) best[i][j] = best[i - 1][j] + a;
else {
int up = best[i - 1][j];
int left = best[i][j - 1];
best[i][j] = (up < left ? up : left) + a;
}
}
}
cout << best[n][m] << endl;
return 0;
}This is the pattern behind path problems of every shape: forbid different directions, change the toll, ask for the maximum — the table does not care. The one-dimensional cousin of "best value ending here" is Maximum Subarray Sum, worth reading side by side with this one.
Deep dive
Why this works
Movement is restricted to right and down, so each cell has exactly two possible predecessors: above and left. The cheapest way to stand on (i, j) is therefore a[i][j] plus the cheaper of the two cheapest arrivals — compute that for every cell in row-major order and best[n][m] is the answer, no search needed.
The cost
O(n·m) time and space: each cell does one min and one addition. For 10×10 that is 100 cells; even a 1000×1000 grid is a million cells, still instant.
Where it goes wrong
- Border cells have only one past: the first row must be a running sum from the left, the first column from above. Setting them equal to the grid values instead is the most common wrong answer.
- Choosing min(up, left) but forgetting to add a[i][j] itself — every cell's toll is mandatory, including the start cell.
- Greedy stepping (always move to the cheaper neighbour) feels right and fails: an expensive step can unlock a cheap corridor. The table never regrets because it computes all cells before any is needed.
Next step
The 1D version of the same idea — best value ending here, no table needed — is Maximum Subarray Sum. For counting rectangles instead of paths, see 2D Range Sums.
Two things to remember
- best[i][j] = a[i][j] + min(from above, from left) — two pasts, pick one.
- Borders accumulate; they have no second direction to take a min over.
🐞 This version fails — open it and try
Leaves the border cells at their grid values — the first row never accumulates
#include <iostream>
using namespace std;
int best[12][12];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int a;
cin >> a;
if (i == 1 && j == 1) best[i][j] = a;
else if (i == 1) best[i][j] = a; // bug: no accumulation
else if (j == 1) best[i][j] = a; // bug: no accumulation
else {
int up = best[i - 1][j];
int left = best[i][j - 1];
best[i][j] = (up < left ? up : left) + a;
}
}
}
cout << best[n][m] << endl;
return 0;
}