2D DP — Reasoning Check

Apply the module invariants, traces, and boundary conditions.

Get every question correct to pass this checkpoint. You can review feedback, revise your answers, and submit again.

1. A grid uses 1 for an obstacle and 0 for an open cell: [[0,0,1,0],[0,0,0,0],[0,1,0,0]]. How many paths go from top-left to bottom-right using only right and down moves? Enter one integer.

2. For costs [[2,8,1],[1,3,1],[4,1,2]], what is the minimum top-left-to-bottom-right path sum using only right and down moves and including both endpoint costs? Enter one integer.

3. A bottom-up triangle DP has lower-row costs [4,1,9] and current-row values [5,2]. Which in-place update order and resulting first two costs are correct?

Select one answer.

Update right to left, producing [8,3]. Update left to right, producing [6,3]. Either direction is equivalent and must produce [6,3]. Update left to right, producing [9,3].

4. For edit distance from "cab" to "cb", the previous DP row E(2,j) is [2,1,1]. While computing E(3,2), which value is the diagonal predecessor and what result follows?

Select one answer.

New E(3,1)=2, giving E(3,2)=2 because both cells share the current row. Old E(2,1)=1, giving E(3,2)=1 because the final b bytes match. Old E(2,2)=1, plus one for replacing b with b, giving E(3,2)=2. Zero, because matching final bytes erase the cost of the earlier prefixes.

5. Can s3="aaxyab" interleave s1="aab" and s2="axy" while preserving each source order?

Select one answer.

No: choosing both initial a characters from s1 gets stuck, so all interleavings fail. No: switching between source strings more than once is forbidden. Yes: any target with the combined character counts is automatically an interleaving. Yes: take the first a from s1, then axy from s2, then the remaining ab from s1.

6. For the binary matrix with rows "1110", "1111", and "0111", what are the maximal-square side length ending at the bottom-right cell and the largest square area anywhere?

Select one answer.

Ending side 2; global area 4. Ending side 3; global area 9. Ending side 1; global area 1. Ending side 4; global area 16.

Auto-advance on pass

Join Discord