Skip to content

Paths in a Grid

Many problems reduce to counting or optimizing paths on a grid with moves (often only right and down), or with costs / obstacles.

Count paths (only right/down)

From \((0,0)\) to \((n-1,m-1)\) in an \(n \times m\) grid, only moving right or down:

\[ \text{dp}[i][j] = \text{dp}[i-1][j] + \text{dp}[i][j-1] \]

with dp[0][0] = 1 and careful handling of blocked cells (0 if blocked).

#include <vector>
using namespace std;

long long countPathsNoObstacles(int n, int m) {
    vector<vector<long long>> dp(n, vector<long long>(m, 0));
    dp[0][0] = 1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (i == 0 && j == 0) continue;
            long long ways = 0;
            if (i > 0) ways += dp[i - 1][j];
            if (j > 0) ways += dp[i][j - 1];
            dp[i][j] = ways;
        }
    return dp[n - 1][m - 1];
}

Minimum path sum

If each cell has a cost, minimize sum along a path from top-left to bottom-right:

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

Obstacles

If blocked[i][j] is true, set dp[i][j] = 0 (or skip transitions into it).

Space optimization

Only the previous row (or column) is needed for transitions from above and left—reduce to \(O(m)\) space.