A path through this grid is a string, and the only thing that matters about the part already walked is how many open brackets are still unclosed. Not which cells you stepped on, not in what order. One integer. That collapse is the problem. The instinct to reject is enumerating paths. A 100x100 grid holds `C(198, 99)` of them, a 58-digit number. Depth-first search with a cutoff on a negative count looks survivable until you notice it keeps arriving at the same cell carrying the same count by a different route, and redoing identical work every time. So the state is `(i, j, open)`, at most `100 * 100 * 199` of those, roughly two million, each either reachable or not. Since the third coordinate is a small integer and the value stored is a single bit, the set of counts reachable at one cell is a bitmask: a `(` on that cell shifts the mask up one position, a `)` shifts it down. `bitset<201>` turns the inner loop over counts into one shift. Two rejections come for free before any of that. The path covers `m + n - 1` cells, an odd-length parentheses string is never valid, so an even `m + n` is an immediate false. And the corners are forced: `grid[0][0]` has to be `(`, `grid[m-1][n-1]` has to be `)`. ## Worked example Take the 4x3 grid from the statement, rows `(((`, `)()`, `(()`, `(()`, and write each cell as the set of open-bracket counts reachable there. The first row only moves right, so it climbs `{1}`, `{2}`, `{3}`. Cell `(1,0)` holds a `)` reached from `{1}`, giving `{0}`. Cell `(1,1)` holds a `(` whose predecessors contribute `{2}` from above and `{0}` from the left, so shifting up gives `{1,3}`. The cell to watch is `(2,2)`. Its predecessors offer `{0,2}` from above and `{2,4}` from the left, union `{0,2,4}`, and the cell holds a `)`. Shifting down gives `{1,3}` - the 0 fell off the bottom of the bitset, and that dropped bit is precisely the route that tried to close a bracket with nothing open. No check was written for it. By the last cell `(3,2)` the predecessors give `{1,3,5}`, the `)` shifts that to `{0,2,4}`, bit 0 is set, true. The two witnesses the statement names, `()(())` and `((()))`, are two of the routes landing on that bit. ## Complexity - Time O(m * n * (m + n) / 64) - one bit per state, and the counts at a cell advance 64 at a time inside a machine word. - Space O(m * n * (m + n) / 8) bytes, about 320 KB on the largest grid - the whole table stays live because I never bothered to keep only the previous row. ## Code (C++) ```cpp class Solution { public: bool hasValidPath(vector>& grid) { int m = grid.size(), n = grid[0].size(); if ((m + n) % 2 == 0) return false; if (grid[0][0] == ')' || grid[m - 1][n - 1] == '(') return false; // dp[i][j] = set of open-bracket balances reachable at (i, j) vector>> dp(m, vector>(n)); dp[0][0][1] = 1; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (i == 0 && j == 0) continue; bitset<201> prev; if (i) prev |= dp[i - 1][j]; if (j) prev |= dp[i][j - 1]; dp[i][j] = grid[i][j] == '(' ? (prev << 1) : (prev >> 1); } } return dp[m - 1][n - 1][0]; } }; ``` ## One note The shift doing the pruning is the part to keep. `prev >> 1` moves count 1 to 0, 2 to 1, and count 0 off the end of the bitset, and that discarded bit is the path that met a `)` with nothing open. The `if (balance < 0) return;` you would write in the recursive version is not an optimization here, it is a side effect of the container. Width is where I would expect to get burned. `bitset<101>` is tempting, since the count cannot pass 100 on a 100-wide grid, and it even happens to be correct: a count larger than the number of moves remaining can never return to zero, which caps the useful range at half the path length. But a bitset that is too narrow discards its high bits in silence. No crash, no warning, just a false where a true belonged. Sizing to the full path length, `m + n - 1` and so at most 199, means I do not have to be right about the tighter bound. Two things to carry off. When the innermost dimension of a DP is a bounded integer and the value stored is one bit, that dimension becomes a bitset and a uniform +1/-1 transition becomes a shift; the same rewrite works on subset-sum reachability, where the shift is by the item's weight instead. And check parity before writing any DP at all - here one comparison kills half the possible inputs.