539. 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).

Constraints - `1 ≤ n ≤ 200` - `-100 ≤ value ≤ 100`