Introduction

Finding the minimum-cost path through a grid is a standard optimization problem. In the common version, each cell has a traversal cost, you start at the top-left cell, you want to reach the bottom-right cell, and you may move only right or down.

Dynamic Programming for Right-and-Down Movement

If movement is restricted to right and down, dynamic programming is the right tool. The best cost to reach a cell depends only on the best cost to reach the cell above it and the cell to the left of it.

That gives a simple recurrence:

• cost at start is the value of the start cell
• cost of first row comes only from the left
• cost of first column comes only from above
• every other cell uses the smaller of top and left, plus the current cell cost

Computing the Minimum Cost

The following C++ example computes the minimum total cost:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int minCost(const std::vector<std::vector<int>>& grid) {
6    if (grid.empty() || grid[0].empty()) {
7        return 0;
8    }
9
10    int rows = static_cast<int>(grid.size());
11    int cols = static_cast<int>(grid[0].size());
12    std::vector<std::vector<int>> dp(rows, std::vector<int>(cols, 0));
13
14    dp[0][0] = grid[0][0];
15
16    for (int c = 1; c < cols; ++c) {
17        dp[0][c] = dp[0][c - 1] + grid[0][c];
18    }
19
20    for (int r = 1; r < rows; ++r) {
21        dp[r][0] = dp[r - 1][0] + grid[r][0];
22    }
23
24    for (int r = 1; r < rows; ++r) {
25        for (int c = 1; c < cols; ++c) {
26            dp[r][c] = std::min(dp[r - 1][c], dp[r][c - 1]) + grid[r][c];
27        }
28    }
29
30    return dp[rows - 1][cols - 1];
31}
32
33int main() {
34    std::vector<std::vector<int>> grid = {
35        {1, 3, 1},
36        {1, 5, 1},
37        {4, 2, 1}
38    };
39
40    std::cout << minCost(grid) << '\n'; // 7
41}

For the sample grid, the cheapest path is 1 -> 3 -> 1 -> 1 -> 1, for a total cost of 7.

Reconstructing the Path

Sometimes the total cost is not enough; you also need the path itself. To do that, keep a parent direction for each cell while filling the DP table.

1#include <algorithm>
2#include <iostream>
3#include <string>
4#include <vector>
5
6struct Result {
7    int cost;
8    std::vector<std::string> path;
9};
10
11Result minCostPath(const std::vector<std::vector<int>>& grid) {
12    int rows = static_cast<int>(grid.size());
13    int cols = static_cast<int>(grid[0].size());
14
15    std::vector<std::vector<int>> dp(rows, std::vector<int>(cols, 0));
16    std::vector<std::vector<char>> parent(rows, std::vector<char>(cols, 'S'));
17
18    dp[0][0] = grid[0][0];
19
20    for (int c = 1; c < cols; ++c) {
21        dp[0][c] = dp[0][c - 1] + grid[0][c];
22        parent[0][c] = 'L';
23    }
24
25    for (int r = 1; r < rows; ++r) {
26        dp[r][0] = dp[r - 1][0] + grid[r][0];
27        parent[r][0] = 'U';
28    }
29
30    for (int r = 1; r < rows; ++r) {
31        for (int c = 1; c < cols; ++c) {
32            if (dp[r - 1][c] <= dp[r][c - 1]) {
33                dp[r][c] = dp[r - 1][c] + grid[r][c];
34                parent[r][c] = 'U';
35            } else {
36                dp[r][c] = dp[r][c - 1] + grid[r][c];
37                parent[r][c] = 'L';
38            }
39        }
40    }
41
42    std::vector<std::string> path;
43    for (int r = rows - 1, c = cols - 1; ; ) {
44        path.push_back("(" + std::to_string(r) + ", " + std::to_string(c) + ")");
45        if (r == 0 && c == 0) {
46            break;
47        }
48        if (parent[r][c] == 'U') {
49            --r;
50        } else {
51            --c;
52        }
53    }
54
55    std::reverse(path.begin(), path.end());
56    return {dp[rows - 1][cols - 1], path};
57}

This version gives both the optimal cost and the coordinates used to achieve it.

When Dynamic Programming Is Not Enough

The DP approach relies on the restricted move set. If the problem allows movement in four directions, or if some edges are blocked, the grid becomes a shortest-path graph problem. In that case, Dijkstra's algorithm is usually the better choice for non-negative weights.

That distinction matters because many bugs come from applying the right-and-down solution to a problem statement that quietly allows more movement.

Common Pitfalls

Forgetting to include the starting cell cost changes the answer by a constant amount and makes test cases fail unexpectedly.

Using the right-and-down DP approach when the problem allows up or left movement gives incorrect results.

Assuming negative costs are safe can break reasoning about optimal paths. Dynamic programming may still work in the restricted move case, but shortest-path variants need more care.

Skipping path reconstruction details often leads to a correct cost with no usable route output.

Index mistakes in the first row and first column are common because those base cases have only one predecessor.

Summary

• For grids where you can move only right and down, dynamic programming is the standard minimum-cost solution.
• Store cumulative cost in a DP table, then take the smaller predecessor for each cell.
• Add a parent table if you also need the actual path.
• Use Dijkstra instead when the move rules are broader than right and down.
• Handle base cases carefully, especially the first row and first column.