Paths in a grid (DP — Grid Sub-pattern)

// Grid paths in one row: moves go right or down only.
// Before the update dp[c] is the cell ABOVE; dp[c - 1] is already the new cell to the LEFT.

// Number of ways from the top-left to the bottom-right (1 = blocked).
long long countPaths(const vector<vector<int>>& blocked) {
    int m = blocked.size(), n = blocked[0].size();
    vector<long long> dp(n, 0);
    dp[0] = 1;
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) {
            if (blocked[r][c]) dp[c] = 0;            // no path goes through an obstacle
            else if (c > 0) dp[c] += dp[c - 1];      // above (old dp[c]) + left (dp[c - 1])
        }
    return dp[n - 1];
}

// Cheapest path: same order, min instead of +.
int minPathCost(const vector<vector<int>>& cost) {
    int m = cost.size(), n = cost[0].size();
    vector<int> dp(n, INT_MAX);
    dp[0] = 0;
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) {
            int best = dp[c];                        // from above
            if (c > 0) best = min(best, dp[c - 1]);  // from the left
            dp[c] = best + cost[r][c];
        }
    return dp[n - 1];
}