Minimum Cost Path Dynamic Programming in C++

In a right-and-down grid, each route adds the costs of the cells it visits. Minimum cost path dynamic programming compares the best totals from above and the left to find the lowest total for each cell.

I’ll show how to fill the cost table and reconstruct a route from the recorded predecessor choices.

TL;DR

For a rectangular grid where each move goes right or down, set each cell’s minimum total to its own cost plus the smaller total above or to its left.

• Initialize the top-left cell with its own cost and accumulate the first row and column along their only possible routes.
• Fill the remaining cells in row-major order in O(rows × columns) time.
• Store each chosen predecessor if the output must include a route, not only its cost.

What Is a Minimum Cost Path in a Grid?

A minimum cost path is a top-left to bottom-right route with the smallest sum of visited-cell costs, where movement is restricted to right and down.

The total includes both endpoints. Define dp[r] as the least cost to reach cell (r, c) from the top-left.

Each legal move increases a row or column index, so the grid has no cycle under these rules.

The following table shows each cell’s minimum accumulated cost, with the destination total at bottom right.

At (1, 1), the predecessor totals are 6 and 8, so the cell receives total 7.

A route arriving at (r, c) must come from (r – 1, c) or (r, c – 1). Add cost[r] to the cheaper valid prefix.

Scan rows from top to bottom and columns from left to right. Each dependency is then computed before the cell that uses it.

For the sample, one minimum route takes costs 1, 5, 1, 1, and 3. Their sum is 11. Another route may tie on a different grid, so a minimum total does not always identify a unique route.

Read the table by rows. The first row accumulates to 1, 6, and 8 because each cell can only follow the cell on its left.

The first value in the next row is 8, reached from the value 1 above. At the middle cell, the total 6 from above beats 8 from the left. Adding the middle cell’s cost of 1 produces 7.

On the final row, the first cell is forced down from 8 to 16. The middle cell chooses 7 from above instead of 16 from the left, producing 8.

At the destination, both predecessor totals are 8. The program’s tie rule chooses the cell above, then adds the destination cost of 3 for a final total of 11.

How to Find a Minimum Cost Path in C++ Step by Step

A two-dimensional table keeps the cell totals available because route reconstruction needs to follow the selected predecessor for every step.

Step 1: Define the grid and DP state

Represent each row as a vector of integer costs. The example uses a fixed input grid so its result is reproducible. For user input, read the row and column counts first and then fill the same vector structure.

const std::vector<std::vector<int>> cost{{1, 5, 2}, {7, 1, 1}, {8, 1, 3}};
const int rows = static_cast<int>(cost.size());
const int cols = static_cast<int>(cost.front().size());
std::vector<std::vector<int>> dp(rows, std::vector<int>(cols));
std::vector<std::vector<char>> came_from_top(rows, std::vector<char>(cols, false));

The dp table stores accumulated costs. The came_from_top table stores whether the selected route entered from above, with false meaning it came from the left. This second table preserves the choice needed for route reconstruction.

Step 2: Set the start and boundary cells

The start has no predecessor, so its best total is its own value. Each top-row cell has only a left predecessor, and each first-column cell has only an above predecessor. Initializing those boundaries explicitly prevents an invalid array access at row or column zero.

dp[0][0] = cost[0][0];
for (int r = 0; r < rows; ++r) {
    for (int c = 0; c < cols; ++c) {
        if (r == 0 && c == 0) continue;
        if (r == 0) {
            dp[r][c] = dp[r][c - 1] + cost[r][c];
        } else if (c == 0) {
            dp[r][c] = dp[r - 1][c] + cost[r][c];
            came_from_top[r][c] = true;
        }
    }
}

The loop skips the origin and fills the boundaries from their single legal predecessors. Interior cells use the next transition. This keeps r – 1 and c – 1 in range.

Step 3: Choose the cheaper predecessor for each interior cell

The following comparison updates each interior entry and records the selected parent for the route output.

else if (dp[r - 1][c] <= dp[r][c - 1]) {
    dp[r][c] = dp[r - 1][c] + cost[r][c];
    came_from_top[r][c] = true;
} else {
    dp[r][c] = dp[r][c - 1] + cost[r][c];
}

The less-than-or-equal comparison makes ties deterministic by choosing the route from above. Either choice keeps the total minimum, while the exact route can vary when paths tie. This parent choice must match the comparison that sets dp[r], or the printed route could fail to match the reported minimum.

Step 4: Reconstruct and run the route

Save the complete program as min_cost_path.cpp. Its initialization and parent tracking fit together as follows.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    const std::vector<std::vector<int>> cost{{1, 5, 2}, {7, 1, 1}, {8, 1, 3}};
    const int rows = static_cast<int>(cost.size());
    const int cols = static_cast<int>(cost.front().size());
    std::vector<std::vector<int>> dp(rows, std::vector<int>(cols));
    std::vector<std::vector<char>> came_from_top(rows, std::vector<char>(cols, false));

    dp[0][0] = cost[0][0];
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (r == 0 && c == 0) continue;
            if (r == 0) {
                dp[r][c] = dp[r][c - 1] + cost[r][c];
            } else if (c == 0) {
                dp[r][c] = dp[r - 1][c] + cost[r][c];
                came_from_top[r][c] = true;
            } else if (dp[r - 1][c] <= dp[r][c - 1]) {
                dp[r][c] = dp[r - 1][c] + cost[r][c];
                came_from_top[r][c] = true;
            } else {
                dp[r][c] = dp[r][c - 1] + cost[r][c];
            }
        }
    }

    std::vector<int> path;
    int r = rows - 1, c = cols - 1;
    while (r != 0 || c != 0) {
        path.push_back(cost[r][c]);
        if (came_from_top[r][c]) --r;
        else --c;
    }
    path.push_back(cost[0][0]);
    std::reverse(path.begin(), path.end());

    std::cout << "Minimum cost: " << dp[rows - 1][cols - 1] << '\\n';
    std::cout << "Path costs: ";
    for (std::size_t i = 0; i < path.size(); ++i) {
        if (i) std::cout << " -> ";
        std::cout << path[i];
    }
    std::cout << '\\n';
}

Compile and run this file with the command below. It uses C++17 standard library features only.

g++ -std=c++17 -O2 -Wall -Wextra -pedantic min_cost_path.cpp -o min_cost_path && ./min_cost_path

ninad@codeforgeek:~$ g++ -std=c++17 -O2 -Wall -Wextra -pedantic min_cost_path.cpp -o min_cost_path && ./min_cost_path
Minimum cost: 11
Path costs: 1 -> 5 -> 1 -> 1 -> 3

The run returns a total of 11 and one route whose cell costs add to that total.

Each of the rows and columns is visited once, so the program takes O(rows × columns) time and stores O(rows × columns) state when route reconstruction is enabled. If only the total is needed, a single row can keep O(columns) values.

The number of legal routes grows quickly with grid dimensions, which is why enumerating every route is a poor strategy. Dynamic programming merges routes that reach the same cell: once their costs are compared, only the best prefix needs to remain for future cells. The table therefore avoids repeating the same downstream work for many different prefixes.

For route output, the parent choice is sufficient because each step has two possible predecessors. Starting at the destination, follow those choices until reaching the origin, then reverse the collected cells.

On a tie, the comparison in the program selects the cell above. Changing less-than-or-equal to less-than would select the left cell on ties instead. Both policies preserve the same minimum total, but tests should compare route cost and legality rather than require a particular route when ties exist.

For input from standard input, parse dimensions before allocating the grid and verify that both are positive. Then read exactly rows times columns values and detect a failed extraction. This separates malformed input handling from the recurrence and prevents the example’s fixed-grid assumptions from being mistaken for input validation.

The parent table uses one small direction value per cell. Backtracking begins at the destination because every saved direction points to the previous cell on a minimum route. The collected costs are in reverse order, so reversing them restores the start-to-finish sequence.

A one-row version stores the running totals in a vector named best.

That order matters in the one-row version. Iterate columns from left to right so the current row’s left value is available. The version saves memory when only the total is needed, but it cannot print a route because it discards predecessor choices.

Edge Cases for Minimum Cost Path

Boundary cases reveal whether the movement rule and table initialization match the problem. This implementation assumes a non-empty rectangular grid and permits non-negative cell costs, matching the common minimum-path-sum formulation.

A greedy walk that chooses the cheaper adjacent cell can fail because that choice ignores costs farther ahead. Dynamic programming compares complete best-prefix totals at each cell, rather than choosing based only on the next cell’s value.

A small cell to the right may lead to expensive cells, while a larger cell below may lead to a cheaper continuation. Compare the accumulated dp values for those choices.

Negative cell costs remain valid when moves are limited to right and down. The move graph has no cycle, so a route cannot loop to collect a negative value repeatedly. Use a numeric type with enough range for the largest possible sum, including negative values if the input allows them.

Before indexing the grid, validate that it has at least one row and that its rows have equal, non-zero width. The example initializes cols from cost.front(), which is safe only after those input conditions hold. For input-driven programs, reject malformed dimensions rather than allowing an out-of-range access.

When obstacles are present, mark unreachable cells and exclude them from the predecessor minimum. A sentinel such as a large numeric value needs care: adding a cost to that sentinel can overflow. Check reachability before addition, and report that the destination is unreachable if both predecessor routes are blocked.

If movement can go up, down, left, and right, a cell may depend on another cell later in row-major order. Model that variant as a graph and choose a shortest-path method suited to its edge weights instead of reusing this recurrence unchanged.

After changing the move set, test a one-cell grid, a single row, a single column, a tie between predecessors, and a grid where the globally cheaper route begins with a locally larger cell. Those cases check boundaries, deterministic parents, and whether the algorithm matches the intended movement rule.

Check that the input has at least one row, that every row has the same number of columns, and that additions fit the selected integer type. For large values or dimensions, use a wider type such as long long and validate the problem’s maximum possible path sum before relying on a bound.

A version that permits diagonal steps needs the above-left predecessor too, while a version with arbitrary up, down, left and right moves is a general graph shortest-path problem rather than this one-pass grid DP.

If the next exercise is counting routes through blocked cells rather than minimizing their cost, CodeForGeek’s Robot and Paths problem in C++ uses a different DP value: the number of ways to reach a cell.

Conclusion: Keep the Move Rules in the State

For a second dynamic-programming example in C++, see CodeForGeek’s Fibonacci article, where states represent sequence indices rather than grid cells.

Write down the legal moves before adapting the recurrence.

FAQ

These answers separate the common right/down grid task from variants that change what the program computes.