Grid DP

Overview

Grid DP is the most visual form of the technique: each cell's answer depends on the cells above and to the left, so filling the grid row by row means every dependency is already computed when you need it. Counting paths sums the two incoming directions; minimum path sum takes the cheaper incoming direction and adds the current cell's cost. Because a cell only ever looks up and left, a single row of values can be updated in place as you sweep — the whole grid collapses to O(cols) memory.

Why it matters

This shape covers far more than toy grid puzzles: dynamic programming over a 2-D state space is how sequence alignment, image seam carving, robot path planning on a cost map, and many scheduling problems are solved. The rolling-row trick you learn here is the same reduction that makes long-sequence alignment feasible in memory.

Core concepts

The dependency direction. With moves restricted to right and down, cell (i,j) depends only on (i-1,j) and (i,j-1). Sweeping top-to-bottom, left-to-right satisfies both dependencies before use — the ordering is the algorithm.

Counting paths. dp[i][j] = dp[i-1][j] + dp[i][j-1], with the first row and first column all 1 (only one way to travel along an edge).

Minimum path sum. dp[i][j] = g[i][j] + min(dp[i-1][j], dp[i][j-1]), with the first row and column being running totals rather than 1s — different base cases for a different question.

Rolling row. In the sweep, dp[j] still holds the value from the row above (that is dp[i-1][j]) while dp[j-1] has already been updated to the current row (dp[i][j-1]). So dp[j] += dp[j-1] for counting, or dp[j] = g + min(dp[j], dp[j-1]) for the minimum, is exactly right — one array, updated in place.

Counts explode. The number of paths across an m x n grid is a binomial coefficient; a 20x20 grid already exceeds 32 bits. Use long long.

Obstacles. Blocked cells set dp[j] = 0 for counting (nothing reaches them) or an INF sentinel for minimisation — and the sentinel must be guarded before adding.

Syntax notes

#include <stdlib.h>

/* number of right/down paths across an r x c grid - rolling row */
long long paths(int r, int c) {
    long long *dp = malloc((size_t)c * sizeof *dp);
    if (!dp) return -1;
    for (int j = 0; j < c; j++) dp[j] = 1;    /* first row: one way along the edge */
    for (int i = 1; i < r; i++)
        for (int j = 1; j < c; j++)
            dp[j] += dp[j-1];                 /* dp[j] = from above, dp[j-1] = from left */
    long long res = dp[c-1];
    free(dp);
    return res;
}

Key points:

• Before dp[j] += dp[j-1] runs, dp[j] is still the row above and dp[j-1] is already this row — that is what makes one array sufficient.
• j starts at 1 because column 0 always keeps its edge value.
• long long: a 20x20 grid has about 35 billion paths.

Lesson

On a grid where you move only right or down, DP answers how many paths reach the bottom-right and the minimum-cost path. Each cell depends only on the cell above and the one to its left — a clean 2-D recurrence (and, for counting, Pascal's triangle).

Code examples

#include <stdio.h>
#include <stdlib.h>
static long long paths(int r,int c){long long*dp=malloc(c*sizeof(long long));for(int j=0;j<c;j++)dp[j]=1;for(int i=1;i<r;i++)for(int j=1;j<c;j++)dp[j]+=dp[j-1];long long v=dp[c-1];free(dp);return v;}
static int minsum(const int*g,int r,int c){int*dp=malloc(c*sizeof(int));dp[0]=g[0];for(int j=1;j<c;j++)dp[j]=dp[j-1]+g[j];for(int i=1;i<r;i++){dp[0]+=g[i*c];for(int j=1;j<c;j++){int u=dp[j],l=dp[j-1];dp[j]=(u<l?u:l)+g[i*c+j];}}int v=dp[c-1];free(dp);return v;}
int main(void){
    printf("unique paths in a 3x7 grid = %lld\n", paths(3,7));
    int grid[]={1,3,1, 1,5,1, 4,2,1};
    printf("min path sum (3x3) = %d\n", minsum(grid,3,3));
    return 0;
}

Line by line

Common mistakes

Recomputing overlapping subpaths recursively; row-major indexing slips.

Debugging tips

Compiler errors and warnings:

• warning: integer overflow, or silently wrong big numbers — the table is int instead of long long.
• -Wsign-compare mixing int bounds with size_t.

Runtime symptoms:

• All results are 1. You never ran the row loop (r was 1), or you reset dp at the top of each row.
• Counts are far too small and wrap negative. int overflow; a 20x20 grid needs 64 bits.
• Off-by-one on the answer. You returned dp[c] instead of dp[c-1], reading past the end.
• Minimum path sum is wrong along the edges. You initialised the first row/column to 1 (the counting base case) instead of running totals.
• Obstacles ignored. You must explicitly zero (or INF) the blocked cell inside the loop; the recurrence will otherwise route straight through it.

Technique: work a 3x3 grid by hand — the answer is 6 paths — and print the rolling array after each row. The sequence {1,1,1} -> {1,2,3} -> {1,3,6} is unmistakable.

Memory safety

• Validate the dimensions before allocating. (size_t)c * sizeof *dp with a negative or zero c either wraps to an enormous request or allocates nothing that is then indexed. Reject r < 1 || c < 1 up front.
• Check the allocation and free on every path, including error returns.
• malloc is fine only because row 0 is fully written by the initialisation loop. If you skip that loop, every subsequent read is of indeterminate memory.
• Index bounds. The answer is dp[c-1]; dp[c] is one past the end. The inner loop must start at j = 1 so dp[j-1] is never dp[-1].
• Overflow of the answer itself. Path counts grow binomially — long long handles a 30x30 grid, but a 60x60 grid needs big integers or a modulus.

Real-world uses

Concrete uses: Seam carving resizes images by finding a minimum-energy path down a grid. Robot and game pathfinding on a cost map uses the same sweep when movement is monotone. Sequence alignment is grid DP with strings on the axes. Spreadsheet dependency evaluation and certain scheduling problems share the shape. Counting-path variants appear in combinatorics and probability.

Professional best practices:

Beginner:

• Write the base row/column deliberately — it differs between counting and minimising.
• Verify against a 3x3 hand computation before scaling up.

Intermediate:

• Use the rolling row whenever you only need the final value; keep the full grid when you must reconstruct the path.
• If movement is not monotone (diagonals, or moving up/left), this sweep is invalid — you need Dijkstra or BFS instead.
• Pick the accumulator from the growth rate: counts are binomial and overflow quickly.

Practice tasks

1. (Beginner) Count paths. Implement long long paths(int r, int c) with the rolling row. Example: 3x3 -> 6; 3x7 -> 28. Concepts: dependency order, base row.

2. (Beginner) Minimum path sum. Implement int minsum(const int *g, int r, int c) where the first row and column are running totals. Example: {{1,3,1},{1,5,1},{4,2,1}} -> 7. Concepts: different base cases, min instead of sum.

3. (Intermediate) Obstacles. Extend the path count so a blocked cell contributes 0. Example: a 3x3 grid with the centre blocked -> 2. Concepts: zeroing unreachable states.

4. (Intermediate) Reconstruct the path. Output the actual cheapest route for the minimum-sum grid. Hint: keep the full grid and walk backwards choosing the smaller predecessor. Concepts: reconstruction, the space trade-off.

Summary

Grid DP works because restricting movement to right and down makes every cell depend only on the cell above and the cell to its left, so a top-to-bottom, left-to-right sweep always has its inputs ready. Counting paths sums the two incoming directions; minimum path sum takes the cheaper one and adds the cell's cost — same sweep, different base cases. A single rolling array suffices because dp[j] still holds the previous row while dp[j-1] already holds the current one. Use long long for counts, validate the dimensions before allocating, and keep the full grid only when you need to reconstruct the route.

Practice with these exercises

• Unique grid paths
• Minimum path sum