450. Falling and Changing Column Each Row
Choose exactly one cell from every row of a grid so that no two cells chosen in ADJACENT rows share a column. Print the smallest possible total.
1 2 3
4 5 6 -> 13 1, then 5, then 7
7 8 9
Values may be negative, so the total may be negative.
Problem 440 lets you move at most one column sideways per row. Here you may jump to ANY other column, and only the immediately previous choice is forbidden. That loosening changes the recurrence and the cost:
dp[i][j] = grid[i][j] + min over t != j of dp[i-1][t]
which is O(r * c^2) as written. It is the same shape as problem 445, and the same
reduction applies: the minimum over t != j is the smallest of the previous row unless
j is where that smallest sits, in which case it is the SECOND smallest. Keeping
both removes the inner scan and gives O(r * c).
Two boundaries worth checking. With c = 1 there is no legal choice for a second
row at all, so the constraint makes the problem infeasible beyond one row; the
bounds therefore require c >= 2 whenever r >= 2. And the first row is
unconstrained, so it seeds the table directly.
Putting this beside 445 is deliberate: identical recurrence, different story, and the same two-smallest trick.
Constraints - `1 ≤ r ≤ 300` - `1 ≤ c ≤ 300` - If `r ≥ 2` then `c ≥ 2`. - `-10000 ≤ value ≤ 10000`
Input
The first line contains two integers r and c.
Each of the next r lines contains c space-separated integers.
Output
Print the smallest total when choosing one cell per row with no two adjacent rows sharing a column.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.