Dynamic Programming Fundamentals: Mastering Grid Walking Problems

Introduction

Many developers encounter dynamic programming for the first time through "grid walking" problems: navigating a two-dimensional grid from start to finish with limited movement options, seeking to count paths, minimize cost, or maximize收益 (gain).

These problems elegantly encapsulate dynamic programming's core concepts. Let's explore them systematically.

Problem 1: Minimum Path Sum

Problem Statement: Given an n × m grid of non-negative integers, start from the top-left corner and reach the bottom-right corner, moving only right or down one step at a time. Sum all numbers along the path. Find the minimum path sum.

Example: Consider this 3×3 grid:

[1, 3, 1]
[1, 5, 1]
[4, 2, 1]

One optimal path: 1 → 3 → 1 → 1 → 1, yielding a sum of 1 + 3 + 1 + 1 + 1 = 7.

Core Insight

If we know the minimum cost to reach preceding cells, we can deduce the minimum cost to reach the current cell.

Define dp[i][j] as the minimum path sum from start to cell (i, j). Since movement is restricted to right or down, the final step to (i, j) must come from:

• Above: (i-1, j), or
• Left: (i, j-1)

Transition Equation:

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + a[i][j]

This embodies DP's essence: current state derives from limited predecessor states.

Initialization

The starting point is simplest:

dp[0][0] = a[0][0]

The first row can only be reached from the left:

dp[0][j] = dp[0][j-1] + a[0][j]

The first column can only be reached from above:

dp[i][0] = dp[i-1][0] + a[i][0]

Traversal Order

Since dp[i][j] depends on above and left cells, naturally fill the table top-to-bottom, left-to-right.

Implementation:

int main() {
    vector<vector<int>> a = {
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1}
    };

    int n = a.size(), m = a[0].size();
    vector<vector<int>> dp(n, vector<int>(m, 0));

    dp[0][0] = a[0][0];

    // Initialize first column
    for (int i = 1; i < n; i++)
        dp[i][0] = dp[i - 1][0] + a[i][0];
    
    // Initialize first row
    for (int j = 1; j < m; j++)
        dp[0][j] = dp[0][j - 1] + a[0][j];

    // Fill remaining cells
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++)
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
    
    cout << dp[n - 1][m - 1] << "\n";
}

Complexity Analysis

• Time Complexity: O(nm) — each cell computed once
• Space Complexity: O(nm) — full 2D table stored

Space Optimization

The space complexity can be reduced significantly.

Key Observation: Examine the transition formula:

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + a[i][j]

When computing row-by-row, at row i:

• dp[i-1][j] represents "same column, previous row"
• dp[i][j-1] represents "current row, left column"

This means computing the current row requires only:

• Previous row's information
• Already-computed left cells in current row

Thus, the 2D array can be compressed to 1D.

1D Array Semantics

Let dp[j] represent "when processing some row, the minimum path sum at column j of that row."

During updates:

• dp[j] before update = previous row's value
• dp[j-1] after update = current row's left value

Therefore:

dp[j] = min(dp[j], dp[j-1]) + a[i][j]

Critical Insight: This demonstrates the rolling array technique's essence—the same array element carries different meanings at different time points.

Optimized Implementation:

int main() {
    vector<vector<int>> a = {
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1}
    };

    int n = a.size(), m = a[0].size();
    vector<int> dp(m, 0);

    // Initialize first row
    dp[0] = a[0][0];
    for (int j = 1; j < m; j++)
        dp[j] = dp[j - 1] + a[0][j];
    
    // Process remaining rows
    for (int i = 1; i < n; i++) {
        dp[0] += a[i][0];  // First column accumulates downward
        for (int j = 1; j < m; j++) {
            dp[j] = min(dp[j], dp[j - 1]) + a[i][j];
        }
    }
    
    cout << dp[m - 1] << "\n";
}

Optimized Complexity

• Time Complexity: O(nm) — unchanged
• Space Complexity: O(m) — reduced from O(nm)

General Principle: Many dynamic programming problems allow space optimization when certain data becomes unnecessary.

Problem 2: Obstacles and Modified Movement

Variation A: Obstacles

Some cells are obstacles and cannot be traversed. Other cells have costs. Movement remains right or down only. Find minimum path sum from top-left to bottom-right.

Approach: If (i, j) is an obstacle, that state is invalid—treat it as positive infinity. Otherwise, normal transition applies:

dp[i][j] = {
    +∞,                              if (i,j) is obstacle
    min(dp[i-1][j], dp[i][j-1]) + a[i][j],  otherwise
}

Key Lesson: Dynamic programming isn't about memorizing formulas. First consider "does current state exist?", then "where does it come from?"

Variation B: Diagonal Movement

Another classic enhancement allows diagonal movement (down-right) in addition to right and down. Now reaching (i, j) could come from three positions:

• (i-1, j) — above
• (i, j-1) — left
• (i-1, j-1) — diagonal upper-left

Transition:

dp[i][j] = min{dp[i-1][j], dp[i][j-1], dp[i-1][j-1]} + a[i][j]

Space Optimization Note: Variation A still allows rolling arrays. Variation B requires additionally preserving the "upper-left" old value beyond "above" and "left," but still needs only 1D space ultimately.

Problem 3: Exactly k Special Cells

Now the goal shifts from minimizing cost to counting total paths. Certain cells are "special," and we require paths from top-left to bottom-right passing through exactly k special cells.

Challenge: Recording only current coordinates cannot distinguish:

• Reaching the same position having passed 1 special cell
• Reaching the same position having passed 3 special cells

These scenarios cannot be conflated.

Solution: Define dp[i][j][t] as the number of paths reaching (i, j) having passed exactly t special cells.

Let special(i, j) indicate whether current cell is special (0 or 1). When transitioning from above or left, the special cell count updates accordingly:

dp[i][j][t] = dp[i-1][j][t-special(i,j)] + dp[i][j-1][t-special(i,j)]

This formula holds only when indices are valid. Invalid indices contribute 0.

Implementation:

int main() {
    int n = 3, m = 3, K = 2;
    vector<vector<int>> sp = {
        {0, 1, 0},
        {1, 0, 1},
        {0, 0, 1}
    };

    // 3D DP: [row][col][special_count]
    vector<vector<vector<long long>>> dp(
        n, vector<vector<long long>>(m, vector<long long>(K + 1, 0))
    );

    // Initialize starting position
    if (sp[0][0] <= K)
        dp[0][0][sp[0][0]] = 1;

    // Fill DP table
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 && j == 0) continue;

            int add = sp[i][j];
            for (int t = add; t <= K; t++) {
                if (i > 0)
                    dp[i][j][t] += dp[i - 1][j][t - add];
                if (j > 0)
                    dp[i][j][t] += dp[i][j - 1][t - add];
            }
        }
    }
    
    cout << dp[n - 1][m - 1][K] << "\n";
}

Key Insight: Adding constraints (exactly k special cells) requires additional state dimensions to track the constraint.

Problem 4: Two-Person Grid Walking

Two people simultaneously walk from top-left to bottom-right, each moving only right or down. Each cell has a value, but if both pass the same cell, its value counts only once. Maximize total collected value.

Alternative Interpretation: One person walks from start to end, then returns, with cells not double-counted.

Naive Approach

Define dp[x1][y1][x2][y2] as optimal value when person 1 is at (x1, y1) and person 2 at (x2, y2). This 4D state is cumbersome and inelegant.

State Compression

If both start simultaneously and move one step each turn, when they reach a certain "stage," their total steps must be equal.

Let current total steps be k. Then:

• Person 1 is at (i1, k-i1)
• Person 2 is at (i2, k-i2)

Thus, 4D state compresses to 3D:

dp[k][i1][i2]

Representing maximum value when both have walked k steps, located at respective positions.

Transition

Each person has two choices per step (down or right), yielding four combined transition sources:

1. Both from above
2. Person 1 from above, Person 2 from left
3. Person 1 from left, Person 2 from above
4. Both from left

Current state derives from the maximum of four candidate states, plus current position values. Let positions be (x1, y1) and (x2, y2). New gain is:

gain = {
    a[x1][y1],                          if (x1,y1) = (x2,y2)
    a[x1][y1] + a[x2][y2],              otherwise
}

Implementation:

int main() {
    int n = 3;
    vector<vector<int>> a = {
        {1, 2, 3},
        {0, 4, 5},
        {2, 1, 6}
    };

    const int NEG = -1e9;
    // dp[step][person1_row][person2_row]
    vector<vector<vector<int>>> dp(
        2 * n - 1, vector<vector<int>>(n, vector<int>(n, NEG))
    );

    dp[0][0][0] = a[0][0];

    for (int k = 1; k <= 2 * n - 2; k++) {
        for (int i1 = 0; i1 < n; i1++) {
            for (int i2 = 0; i2 < n; i2++) {
                int j1 = k - i1;
                int j2 = k - i2;
                
                // Validate positions
                if (j1 < 0 || j1 >= n || j2 < 0 || j2 >= n)
                    continue;

                int best = NEG;

                // Four transition sources
                for (int di1 = 0; di1 <= 1; di1++) {
                    for (int di2 = 0; di2 <= 1; di2++) {
                        int pi1 = i1 - di1;
                        int pi2 = i2 - di2;
                        int pj1 = (k - 1) - pi1;
                        int pj2 = (k - 1) - pi2;
                        
                        if (pi1 < 0 || pi2 < 0 || pj1 < 0 || pj2 < 0)
                            continue;
                        
                        best = max(best, dp[k - 1][pi1][pi2]);
                    }
                }

                if (best == NEG) continue;

                int gain = a[i1][j1];
                if (i1 != i2 || j1 != j2)
                    gain += a[i2][j2];
                
                dp[k][i1][i2] = best + gain;
            }
        }
    }
    
    cout << dp[2 * n - 2][n - 1][n - 1] << "\n";
}

Summary: Core Dynamic Programming Concepts

"Grid walking" appears as a narrow problem type but actually concentrates dynamic programming's most essential elements:

Critical Questions for Every DP Problem:

1. What is the state? How many dimensions represent it?
2. Where does current state derive from?
3. What are the boundary and initial conditions?
4. What traversal order ensures dependencies are resolved?
5. Can space be optimized?
6. How do additional constraints affect state design?

Mastering these patterns through grid problems provides a solid foundation for tackling more complex dynamic programming challenges across algorithms and competitive programming.

Further Practice Recommendations

To deepen understanding:

1. Variation Practice: Modify grid problems with different movement rules, obstacles, or objectives
2. Dimension Progression: Start with 1D DP, progress to 2D, then 3D+ states
3. Optimization Challenges: Given working solutions, attempt space/time optimizations
4. Real-World Mapping: Identify DP patterns in practical problems (resource allocation, scheduling, etc.)

Dynamic programming mastery comes through deliberate practice and pattern recognition. Grid walking problems offer an accessible entry point to this powerful algorithmic paradigm.