Falling Without Repeating a Column
Choose exactly one cell from each row of an n by n grid, so that no two cells in
ADJACENT rows share a column. Print the smallest possible total.
1 2 3
4 5 6 -> 13 1 + 5 + 7
7 8 9
Problem #440 lets a fall move to the column directly below or diagonally adjacent. Here the only restriction is "not the same column as the row above", so a choice may jump to ANY other column.
## The recurrence
``` dp[r][c] = the smallest total for rows 0..r with row r using column c
dp[0][c] = g[0][c] dp[r][c] = g[r][c] + min over pc != c of dp[r-1][pc] ```
Written directly that inner minimum is a scan of the previous row, so the whole thing is
O(n^3). At n = 200 that is 8 * 10^6 and passes.
## The two-smallest trick
The inner minimum is "the smallest entry of the previous row, EXCLUDING column c". That
value takes only two possible forms:
c is not where the row minimum sits -> the row minimum
c is where the row minimum sits -> the SECOND smallest
So find the smallest and second smallest of each row once, and each cell becomes O(1),
giving O(n^2).
Recognising that an exclusion-minimum needs only two order statistics is the reusable part. It appears whenever a transition forbids exactly one predecessor.
## The tie that the trick has to survive
If the row minimum is attained at several columns, then excluding one of them still leaves another, so the answer is the minimum, not the second smallest.
Tracking the INDEX of the minimum alongside its value handles this correctly, as long as the
comparison for the second smallest is <= against a different index rather than a strict
comparison on value. 5 5 / 5 5 answers 10 and 2 2 2 / 2 2 2 / 2 2 2 answers 6: all
entries equal, and the exclusion never costs anything.
Those two inputs are tests because a solution that assumes the second smallest is strictly larger overpays on them.
## Negatives
Values may be negative, so the total may be negative. -1 -2 / -3 -4 answers -5, from
-2 then -3. A solution initialising its running minimum to 0 gets this wrong.
## Boundaries
A 1 by 1 grid has a single row, so the adjacency rule never applies and the answer is that
cell. 7 answers 7.
1 99 99 / 99 1 99 / 99 99 1 answers 3: the three cheap cells are on the diagonal and no
two of them share a column, so all three are usable.
## Cost
Time O(n^2) with the two-smallest trick, O(n^3) written directly. Space O(n).