What Is Grid DP and Why Is It Important?

Grid DP (dynamic programming on a grid) is a special class of problems in which we work with a two-dimensional matrix (grid) and want to calculate a value for each cell based on previously calculated cells.

The most common example is the following:

• We are given a matrix of dimensions n × m,
• we start in the top-left corner,
• we want to reach the bottom-right corner,
• we are allowed to move only right or down.

The question is: In how many different ways can we reach the destination?

At first glance, the problem may seem combinatorial, but the number of possible paths quickly becomes enormous. Generating every possible path would be too slow, because the number of combinations grows exponentially.

This is where dynamic programming comes in. Instead of repeating the same calculations, we use the fact that each cell can be reached from a previously visited cell, allowing us to build the result step by step.

Why Is Grid DP Important in Competitions?

Grid DP problems are extremely common in competitive programming and in technical screening tests for IT companies.

• Counting paths through a grid
• Minimum path sum
• Maximum value of collected points
• Problems involving obstacles
• Movement in multiple directions

Understanding this type of problem makes it easier to learn more advanced DP techniques, because it introduces the use of two-dimensional states.

If you have already studied 1D dynamic programming (such as the Fibonacci sequence), Grid DP is a natural next step: instead of one dimension, we now work with two.

This problem often appears in tasks involving movement through a matrix, using related techniques such as BFS (Breadth-First Search) when minimizing the number of steps. For such problems, see the Grid BFS section in the graph algorithms lesson.

For problems involving movement through an unweighted grid (for example, finding the minimum number of steps), also see Grid BFS, which uses graph traversal on a matrix.

Description of the Basic Problem

Consider a rectangular matrix with dimensions n × m. The cells are indexed from (0, 0) to (n−1, m−1).

We start at cell (0, 0) — the top-left corner — and our goal is to reach cell (n−1, m−1) — the bottom-right corner.

Only the following moves are allowed:

• one step to the right (i, j → i, j+1)
• one step down (i, j → i+1, j)

We need to determine how many different ways we can reach the destination cell from the starting cell.

Why Is the Naive Solution Too Slow?

One possible approach would be to recursively generate every possible path. However, the number of paths quickly increases as the matrix dimensions grow.

For example, even for a 20 × 20 matrix, the number of paths is very large, so generating every combination would be extremely slow.

This is why we use dynamic programming: instead of repeating the same calculations, we store the results for every cell.

Defining the DP State

We define a two-dimensional array:

• dp[i][j] represents the number of different paths by which we can reach cell (i, j).

This means that, for every cell, we want to know how many different ways there are to reach it using the permitted moves.

Our final goal is to calculate:

• dp[n-1][m-1]

which represents the total number of different paths to the destination.

DP Transition (Recurrence Relation)

To calculate the value of dp[i][j], we ask: From which cells can we reach cell (i, j)?

Since only two moves are allowed — right and down — we can reach cell (i, j):

• from the cell above: (i-1, j)
• from the cell to the left: (i, j-1)

If we know the number of paths to those cells, the total number of paths to cell (i, j) is equal to the sum of those two numbers.

Therefore, we obtain the basic DP recurrence:

• dp[i][j] = dp[i-1][j] + dp[i][j-1]

Base Cases

For the recurrence to work correctly, we must define the initial values.

• dp[0][0] = 1

  — there is exactly one way to be at the starting cell.

For the first row (i = 0):

• We can move only to the right, so every element is equal to 1.

For the first column (j = 0):

• We can move only down, so every element is also equal to 1.

We have now defined all the conditions needed to fill the entire DP table.

C++ Implementation (With Explanations)

In this program, we solve the classic Grid DP problem: we want to travel from the top-left corner of a matrix with dimensions n × m to the bottom-right corner, moving only right or down.

We create an n × m DP table, where:

• dp[i][j] represents the number of different paths to cell (i, j),
• we can reach each cell either from the cell above (i−1, j),
• or from the cell to the left (i, j−1).

Therefore, the following recurrence applies:

• dp[i][j] = dp[i-1][j] + dp[i][j-1]

Initial state:

• dp[0][0] = 1 — there is exactly one way to be at the starting cell.

The final answer is dp[n-1][m-1], the number of ways to reach the bottom-right corner.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    // n = number of rows
    // m = number of columns

    // Create an n x m DP table
    // dp[i][j] = number of ways to reach cell (i, j)
    vector<vector<int>> dp(n, vector<int>(m, 0));

    // Starting cell
    dp[0][0] = 1;

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

            // If we can reach this cell from above
            if (i > 0)
                dp[i][j] += dp[i-1][j];

            // If we can reach this cell from the left
            if (j > 0)
                dp[i][j] += dp[i][j-1];
        }
    }

    // Final answer
    cout << dp[n-1][m-1];
}

Grid with Obstacles

In many problems, some cells cannot be used because they contain obstacles. In that case:

• If a cell is an obstacle → dp[i][j] = 0
• Otherwise, we use the same recurrence as before.

Before calculating a cell's value, we check whether the cell is allowed. If the starting cell is blocked, the result is 0.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m));
    vector<vector<long long>> dp(n, vector<long long>(m, 0));

    // Read the matrix
    // 0 = free cell
    // 1 = obstacle
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    if (grid[0][0] == 0)
        dp[0][0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {

            if (grid[i][j] == 1) {
                dp[i][j] = 0; // obstacle
                continue;
            }

            if (i > 0)
                dp[i][j] += dp[i-1][j];

            if (j > 0)
                dp[i][j] += dp[i][j-1];
        }
    }

    cout << dp[n-1][m-1];
}

Algorithm Complexity

• Time complexity: O(n × m)
• Space complexity: O(n × m)

Since every cell is calculated exactly once, the algorithm is very efficient and suitable for medium-sized matrices (n and m up to a few thousand).

Memory Optimization

Since we need only the current and previous row for the calculation, we can reduce memory usage from O(n × m) to O(m).

This is a common technique in competitions when the constraints are large.

Example of Filling the DP Table

Consider a simple matrix with dimensions 3 × 3. We want to calculate the number of paths from (0,0) to (2,2).

Initially, we set:

• dp[0][0] = 1
• First row = 1 (movement only to the right)
• First column = 1 (movement only down)

We now calculate the remaining cells using the recurrence:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Cell (1,1):

• We arrive from (0,1) = 1
• We arrive from (1,0) = 1

Therefore:

dp[1][1] = 1 + 1 = 2

Cell (1,2):

• We arrive from (0,2) = 1
• We arrive from (1,1) = 2

dp[1][2] = 1 + 2 = 3

Cell (2,1):

• We arrive from (1,1) = 2
• We arrive from (2,0) = 1

dp[2][1] = 2 + 1 = 3

Finally, cell (2,2):

• We arrive from (1,2) = 3
• We arrive from (2,1) = 3

dp[2][2] = 3 + 3 = 6

Therefore, there are 6 different paths from the top-left to the bottom-right corner of a 3 × 3 grid.

This example clearly shows how the table is built incrementally: each cell depends only on neighbors that have already been calculated.

Implementation (C++)

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    long long dp[n][m];

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(i == 0 && j == 0)
                dp[i][j] = 1;
            else {
                long long fromUp = (i > 0) ? dp[i-1][j] : 0;
                long long fromLeft = (j > 0) ? dp[i][j-1] : 0;
                dp[i][j] = fromUp + fromLeft;
            }
        }
    }

    cout << "Number of paths: " << dp[n-1][m-1];
    return 0;
}

Grid with Obstacles

Some cells may be unusable because they contain obstacles. We can mark obstacles with 1, while free cells are marked with 0.

If a cell contains an obstacle:

dp[i][j] = 0

Example: Grid with Obstacles (C++)

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    int grid[n][m];
    long long dp[n][m];

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> grid[i][j];

    if(grid[0][0] == 1) {
        cout << 0;
        return 0;
    }

    dp[0][0] = 1;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(grid[i][j] == 1) {
                dp[i][j] = 0;
            } else {
                if(i == 0 && j == 0) continue;
                long long fromUp = (i > 0) ? dp[i-1][j] : 0;
                long long fromLeft = (j > 0) ? dp[i][j-1] : 0;
                dp[i][j] = fromUp + fromLeft;
            }
        }
    }

    cout << dp[n-1][m-1];
    return 0;
}

Algorithm Complexity

Let us analyze the efficiency of our solution.

Time Complexity

We fill the DP table of dimensions n × m by calculating each cell exactly once.

For every cell, we perform a constant number of operations (adding two values).

Therefore, the total time complexity is:

• O(n × m)

This is a very efficient solution, because every state is calculated only once.

Space Complexity

We use a two-dimensional table of size n × m, so the space complexity is:

• O(n × m)

This is perfectly acceptable for medium-sized matrices (n and m up to a few thousand).

When Can Problems Occur?

• If the dimensions are extremely large (for example, 10⁵ × 10⁵), memory becomes an issue.
• If the number of paths is very large, the range of the int type may be exceeded.

In such situations, we use:

• the long long variable type
• calculating results modulo a number (for example, 10⁹ + 7)
• memory optimization to O(m)

This makes Grid DP applicable to much larger inputs.

Variant: Minimum Path Sum

In this version of the problem, each cell in the matrix contains a value (a cost).

The goal is no longer to count paths, but to find the minimum possible sum of the values of the cells we pass through from (0,0) to (n−1,m−1).

The permitted moves are still:

• right
• down

Defining the DP State

• dp[i][j] represents the minimum sum needed to reach cell (i, j).

DP Recurrence

Since we can reach cell (i, j) from the cell above or from the left, we choose the path with the smaller sum:

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

Base Cases

• dp[0][0] = grid[0][0]
• The first row is filled by adding values from the left.
• The first column is filled by adding values from above.

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m));
    vector<vector<int>> dp(n, vector<int>(m));

    // Read the matrix
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    dp[0][0] = grid[0][0];

    // Fill the first row
    for (int j = 1; j < m; j++)
        dp[0][j] = dp[0][j-1] + grid[0][j];

    // Fill the first column
    for (int i = 1; i < n; i++)
        dp[i][0] = dp[i-1][0] + grid[i][0];

    // Fill the rest of the table
    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]) + grid[i][j];
        }
    }

    cout << dp[n-1][m-1];
}

Here we can see that the structure of the problem does not change; only the operation changes:

• for counting → addition
• for optimization → minimum (or maximum)

This shows how flexible and powerful Grid DP is.

Variant: Grid with Obstacles

In this version of the problem, some cells in the matrix represent obstacles that cannot be used.

The goal is still to reach cell (n-1,m-1) from cell (0,0), but now we must avoid blocked cells.

We represent obstacles numerically:

• 0 → free cell
• 1 → cell containing an obstacle

Defining the DP State

• dp[i][j] represents the number of paths to cell (i,j) that do not pass through obstacles.

DP Recurrence

If cell (i,j) is free:

• dp[i][j] = dp[i-1][j] + dp[i][j-1]

If the cell is an obstacle:

• dp[i][j] = 0

The starting cell (0,0) is set to 1 only if it is not blocked.

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m));
    vector<vector<long long>> dp(n, vector<long long>(m, 0));

    // Read the matrix
    // 0 = free cell, 1 = obstacle
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    if (grid[0][0] == 0)
        dp[0][0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) {
                dp[i][j] = 0; // obstacle
                continue;
            }
            if (i > 0)
                dp[i][j] += dp[i-1][j];
            if (j > 0)
                dp[i][j] += dp[i][j-1];
        }
    }

    cout << dp[n-1][m-1];
}

This example shows how flexible the basic DP table structure is: only the obstacle condition changes, while the recurrence remains the same.

Variant: Maximum Path Sum

In this version, each cell in the matrix contains a value. The goal is to find the path with the maximum sum of values from (0,0) to (n−1,m−1), moving only right or down.

This variant is similar to the Minimum Path Sum problem, except that we choose the maximum instead of the minimum.

Defining the DP State

• dp[i][j] represents the maximum sum we can collect by reaching cell (i,j).

DP Recurrence

For every cell (i,j), we can arrive from above or from the left:

• dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

Base cases:

• dp[0][0] = grid[0][0]
• The first row is filled by adding values from the left.
• The first column is filled by adding values from above.

C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m));
    vector<vector<int>> dp(n, vector<int>(m));

    // Read the matrix
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    dp[0][0] = grid[0][0];

    // Fill the first row
    for (int j = 1; j < m; j++)
        dp[0][j] = dp[0][j-1] + grid[0][j];

    // Fill the first column
    for (int i = 1; i < n; i++)
        dp[i][0] = dp[i-1][0] + grid[i][0];

    // Fill the rest of the table
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }

    cout << dp[n-1][m-1];
}

This variant shows that the same DP table structure can solve different tasks simply by changing the operation (addition → minimum/maximum, or counting).

Competition Notes and Edge Cases

When solving Grid DP problems in competitions or practice, it is important to pay attention to a few practical details.

1. Variable Type

• The number of paths can become very large very quickly.
• Use long long instead of int when the value exceeds approximately 10⁹.
• If the problem requires modulo arithmetic (for example, 10⁹ + 7), apply the modulo after each addition.

2. The Starting Cell May Be Blocked

• If dp[0][0] is an obstacle, the result is immediately 0.
• The same applies if the destination is blocked — there is no solution.

3. Matrix Dimensions

• For very large matrices (n, m > 10⁴), a two-dimensional table may use too much memory.
• In such cases, use memory optimization: store only the previous row (O(m) space).

4. Edge Cases

• One row or one column — DP reduces to simple addition.
• Negative values in the matrix — minimum or maximum path sums may require careful initialization.
• Obstacles along the edges of the matrix — check the DP recurrence to avoid out-of-bounds access.

5. Advice for Competitors

• First solve the basic problem without obstacles to understand how the table is filled.
• Then add obstacles and sum optimization.
• Always test small examples manually to verify the logic.

Advanced Variant: A Path with Minimum Total Movement

In this version of the problem, each cell in the matrix contains a number of dissenters. Dorm Sletač wants to find a path from cell (0,0) to (n−1,m−1), moving only:

• right
• down

Unlike classic Grid DP problems, the goal is not to minimize the sum of the values on the path itself, but to minimize:

the total distance that all dissenters travel to reach the nearest cell on the chosen path.

Why Is Ordinary DP Not Enough?

In standard problems, we often use the formula:

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

We cannot apply it directly here.

The reason is that the value of grid[i][j] is not known in advance. The cost of a cell does not depend only on that cell, but on:

• all dissenters in the matrix
• their distances to the path
• the way the path extends through the matrix

Therefore, we need to change how we think about the problem.

The Key Idea

Instead of viewing the problem this way:

• "each dissenter looks for the nearest cell on the path"

it is much easier to think about it this way:

• "the path gradually expands through the matrix"

When the path reaches a new cell:

• a new part of a row or column is added
• a group of dissenters reaches the path for the first time
• their contribution to the total cost is calculated exactly once

This gives us a way to use dynamic programming.

How Does the Path "Expand"?

If we reach cell (i,j):

• from above → we add a new part of the current row
• from the left → we add a new part of the current column

It is important to notice:

• we do not process the entire matrix every time ❌
• we process only the "new layer" that has just been added ✔

What Does the DP State Represent?

We use the standard Grid DP idea:

dp[i][j]

It represents:

• the minimum total cost of a path that reaches cell (i,j)

The transition remains similar to ordinary Grid DP:

dp[i][j] =
    min(
        dp[i-1][j] + cost_of_arriving_from_above,
        dp[i][j-1] + cost_of_arriving_from_the_left
    );

The difference is that:

• the "cost" is not given in advance
• we must calculate it efficiently

The Naive Idea — and the Problem

Suppose we arrive at cell (i,j) from above.

We must then add the contribution of all cells:

(i,1), (i,2), ..., (i,j-1)

Each of these cells must move right to column j.

A naive approach would be:

for (k = 1; k < j; k++)
    sum += a[i][k] * (j - k);

But if we do this for every cell in the matrix:

• the complexity becomes too high ❌

Optimization Using Prefix Sums

Instead of visiting every cell individually, we use:

• prefix sums

We store:

• the ordinary sum of elements
• the weighted sum of elements

For example:

sum a[i][k] * (j - k)
=
j * sum(a[i][k]) - sum(a[i][k] * k)

This allows us to:

• calculate the entire sum in O(1)
• without iterating through every cell

What Do the Variables k and r Represent?

The formulas often use the following variables:

• k — the current column in a row
• r — the current row in a column

For example:

sum a[i][k] * (j - k)

means:

• we iterate through all columns k to the left of j
• each cell must move (j-k) steps to the right

Similarly:

sum a[r][j] * (i - r)

• we iterate through all rows r above i
• each cell must move (i-r) steps down

Why Does This Work?

The key property of the problem is:

• dissenters are also allowed to move only: right or down

Therefore:

• each cell "belongs" to exactly one moment when the path first reaches it
• no contribution is counted more than once

This is precisely what makes an efficient DP approach possible.

Common Questions

• ❓ Do we need to remember which cells have already been processed?
  ✔ No — this is implicitly determined by the DP state.
• ❓ Do we traverse the entire column or row every time?
  ✔ No — we use prefix sums and obtain the result in O(1).
• ❓ Is the same dissenter counted more than once?
  ✔ No — each contribution is added exactly once.
• ❓ Would the same approach work if movement to the left or upward were also allowed?
  ✔ Not necessarily — we would no longer have a simple path-expansion process.

Conclusion

This problem is an excellent example of combining:

• dynamic programming
• prefix sums
• careful problem modeling

The most important idea is not the DP formula itself, but:

correctly identifying the new contribution when the path expands.

Once the problem is modeled correctly:

• expensive calculations disappear
• a complex task becomes standard DP with optimizations ✔

Visual Intuition — How the Path "Expands"

The most important idea in this problem is to avoid viewing the path all at once. Instead, we treat it as a process that gradually expands through the matrix.

When the path reaches a new cell:

• a new part of a row or column is added
• only those new cells come into contact with the path for the first time
• we calculate their contribution to the total cost

Arriving from Above

Suppose we arrive from cell (i-1,j) at cell (i,j).

For example:

• i = 4
• j = 3

We therefore arrive at cell:

(4,3)

The path then reaches part of the fourth row for the first time.

When we arrive from above:

• a new part of the row is added
• specifically, the cells: (i,1), (i,2), ..., (i,j)

In the example above, these are:

(4,1), (4,2), (4,3)

All dissenters in those cells must move right to reach column j.

If someone is located at cell:

(i,k)

they must travel:

j - k

steps.

What Does the Variable k Represent?

The variable k represents:

• the current column within the current row

A naive approach would be:

for(int k = 1; k < j; k++) {
    sum += a[i][k] * (j - k);
}

In other words:

• we visit every cell to the left of column j
• and add its contribution

But this would be too slow.

That is why we use prefix sums and the formula:

∑ a[i][k] * (j-k)
=
j * ∑a[i][k] - ∑(a[i][k] * k)

Arriving from the Left

Now suppose we arrive from:

(i,j-1)

at cell:

(i,j)

For example:

• i = 4
• j = 4

Here we add a new column:

(1,j), (2,j), ..., (i,j)

In the example above:

(1,4), (2,4), (3,4), (4,4)

The dissenters must now move down to row i.

If someone is located at:

(r,j)

they must travel:

i - r

steps.

What Does the Variable r Represent?

The variable r represents:

• the current row within the current column

A naive approach would be:

for(int r = 1; r < i; r++) {
    sum += a[r][j] * (i - r);
}

But this would also be too slow for large matrices.

Therefore, we use:

∑ a[r][j] * (i-r)
=
i * ∑a[r][j] - ∑(a[r][j] * r)

Why Is This Important?

• we calculate every contribution exactly once ✔
• we do not traverse the entire matrix at every step ✔
• DP remains efficient ✔
• prefix sums allow calculations in O(1) ✔

Interactive Example — Prefix Sums and a K×K Square

The following example shows how prefix sums work in a matrix.

Hover over a table cell to see:

• the prefix-sum value for that cell
• the sum of the K×K square ending at that cell, if one exists

What Does Each Cell Represent?

Each cell displays:

prefix[i][j]

that is, the sum of all elements in the region:

(0,0) → (i,j)

For example:

prefix[2][2]

contains the sum of all elements in the region:

X X X
X X X
X X X

How Do We Calculate the Sum of a K×K Square?

When we want the sum of a region:

• we do not iterate over every cell in the square ❌
• we use previously calculated prefix values instead ✔

Formula:

sum =
prefix[i][j]
- prefix[i-K][j]
- prefix[i][j-K]
+ prefix[i-K][j-K]

This allows us to:

• calculate each sum in O(1)
• without additional loops

What Should You Notice?

• Prefix sums store information about previous cells ✔
• Large regions can be calculated very quickly ✔
• Instead of adding everything again, we use results that have already been calculated ✔

Connecting This to the Main Problem

In the Dorm Sletač problem:

• we do not calculate only an ordinary sum
• we calculate a sum weighted by distance

But the basic idea remains the same:

• we avoid traversing a large number of cells
• we use precomputed sums
• we obtain the result in constant time

The Key Intuition

You can think of prefix sums as:

• "the memory of the matrix"

They store in advance:

• the sums of previously processed regions
• so that we do not have to traverse the same cells again later

Practice Problems — Dynamic Programming on a Grid

Task 1: Counting Paths in a 3×3 Grid

A grid of dimensions 3 × 3 is given. The only allowed moves are right and down. Determine how many different paths lead from the top-left to the bottom-right corner.

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

1 1 1
1 2 3
1 3 6
    

Task 2: Minimum Path Sum in a 4×4 Grid

A matrix with dimensions 4 × 4 is given:

• {2, 3, 1, 4}
• {5, 6, 2, 1}
• {1, 2, 7, 3}
• {4, 3, 2, 1}

Determine the minimum path sum from the top-left to the bottom-right corner. Allowed moves: right and down.

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

2  5  6 10
7 11  8  9
8 10 15 12
12 13 14 13
    

Task 3: Grid with Obstacles (5×5)

A 5 × 5 matrix is given, where 0 represents a free cell and 1 represents an obstacle. Allowed moves are to the right and down.

0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
1 0 1 0 0
0 0 0 0 0

1 1 1 1 1
1 0 1 0 1
1 1 2 2 3
0 1 0 2 5
0 1 1 3 8

Additional Practice Problems (Advanced)

Task 4: Maximum Path Sum in a 4×4 Grid

A matrix with dimensions 4 × 4 is given, containing the following cell values:

• {1, 2, 3, 4}
• {2, 1, 4, 3}
• {3, 2, 1, 2}
• {4, 3, 2, 1}

Determine the maximum path sum from the top-left to the bottom-right corner. The allowed moves are right and down.

Hint (brief):

dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])
  

Task 5: Maximum Path Sum with Obstacles (5×5)

A 5 × 5 matrix is given, where -1 represents an obstacle that cannot be crossed, while the remaining cells contain values. The only allowed moves are right and down. Find the maximum sum of values along a path from the top-left cell to the bottom-right cell without crossing any obstacles.

0   2   3   4   1
2  -1   1   5   2
3   2  -1   1   3
1   4   2   2   1
2   1   3   1   2

Hint (brief):

dp[0][0] = grid[0][0], if the starting cell is not an obstacle

dp[i][j] = -∞, if grid[i][j] == -1

best = max(dp[i-1][j], dp[i][j-1])
       (cells outside the matrix have value -∞)

dp[i][j] = grid[i][j] + best, if best != -∞
dp[i][j] = -∞, if best == -∞

 0   2   5   9  10
 2   X   6  14  16
 5   7   X  15  19
 6  11  13  17  20
 8  12  16  18  22

0 → 2 → 3 → 4 → 5 → 2 → 3 → 1 → 2

0 + 2 + 3 + 4 + 5 + 2 + 3 + 1 + 2 = 22

Task 6: Competitive Variant — Large Grid with Modulo

A matrix with dimensions 1000 × 1000 is given, with cell values from 0 to 1000. The goal is to find the number of paths from (0,0) to (999,999) such that the sum of cell values is maximum, and calculate the result mod 1e9+7. Allowed moves: right and down.

Hint (brief):

Use a DP table where dp[i][j] = maximum path sum to cell (i,j)
If the sum exceeds 1e9+7, use dp[i][j] % 1e9+7
For memory optimization, store only the previous row (O(m) space)
  

Solution-Checking Template — Tasks 4–6

Tasks 4 & 5 — Maximum Path Sum (Small Matrices)

You can use this template to check your DP tables for smaller matrices (4×4 or 5×5).

Checking the DP Table — C++ Template

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m));
    vector<vector<int>> dp(n, vector<int>(m, 0));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    dp[0][0] = grid[0][0];

    for (int j = 1; j < m; j++)
        dp[0][j] = dp[0][j-1] + grid[0][j];

    for (int i = 1; i < n; i++)
        dp[i][0] = dp[i-1][0] + grid[i][0];

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (grid[i][j] == -1) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    cout << dp[n-1][m-1] << '\n';
}
  

Task 6 — Competitive Variant (Large Grid + Modulo)

For a larger grid (n, m ≤ 1000) and counting modulo 1e9+7, use the following template:

Template — C++ (Large Grid)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MOD = 1e9+7;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m));

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin >> grid[i][j];

    vector<int> prev(m, 0), curr(m, 0);

    prev[0] = grid[0][0];

    for(int j=1;j<m;j++)
        prev[j] = prev[j-1] + grid[0][j];

    for(int i=1;i<n;i++){
        curr[0] = prev[0] + grid[i][0];
        for(int j=1;j<m;j++){
            curr[j] = max(prev[j], curr[j-1]) + grid[i][j];
            if(curr[j] >= MOD) curr[j] %= MOD;
        }
        prev = curr;
    }

    cout << prev[m-1] << '\n';
}
  

Visual DP Table — Task 5 (Grid with Obstacles)

We have marked obstacles with X. Cell dp[i][j] represents the maximum path sum to cell (i,j).

How to read the table:
- Cell dp[1][2] = 6 means that the maximum path sum to cell (1,2) is 6, avoiding obstacles. - A cell marked X is an obstacle, so no path can pass through it. - The destination cell dp[4][4] = 14 gives the maximum path sum through the entire grid.

This table helps students visualize how DP "flows" through the grid, which paths are ignored because of obstacles, and where values are added.

Interactive DP Table — Task 5

Hover over a cell to see where its maximum sum comes from.

Hidden Mini Quiz — Grid DP (2D DP Problem)

Click to test your knowledge of the basics of Grid DP and obstacles!

4. Related Pages

• Introduction to DP — The Basic Idea and Techniques
• DP: Fibonacci with Memoization
• DP: The Subset Sum Problem
• Algorithms — DP in a Broader Context (Recursion and DP)
• Competition Preparation — 2D DP and Advanced Examples

5. External Resources for Further Learning

• Dynamic Programming — GeeksforGeeks (Text Tutorials)
• DP on Grids — GeeksforGeeks Practice and Explanations
• AtCoder Educational DP Contest — Competitive Programming DP Tasks
• Grid-Based DP Tutorials (YouTube Search)
• CP-Algorithms — Advanced DP Concepts (Divide and Conquer, Memory Optimizations)

6. Recommended Books and Online Courses

• "Introduction to Algorithms" (Cormen, Leiserson, Rivest, Stein) — a classic book that covers the DP paradigm and its applications in detail.
• "Competitive Programming 3" (Steven Halim) — practical examples and competitive programming problems involving DP, grid problems, and optimizations.
• MIT OCW 6.006 — Introduction to Algorithms — a free online course with lectures, problem sets, and DP lessons.
• Coursera: Algorithms Part I (Princeton) — detailed coverage of basic and advanced DP problems through practical exercises.
• freeCodeCamp — Dynamic Programming for Beginners — an interactive tutorial with visual examples and practical exercises.