440. The Cheapest Fall Through a Rectangle
Start at ANY cell of the top row of a grid and fall to the bottom row. From a cell you may step to the cell directly below, or to the one below-left, or the one below-right. Print the smallest total of the values visited.
Values may be negative, so the answer may be negative.
Problem #417 is the triangle version, where the shape restricts the moves and the start is fixed at the single top entry. Here the start is free and every row has the same width, which changes two things: every column of the top row must be tried, and the answer is the smallest entry of the LAST row rather than a single corner.
dp[0][j] = grid[0][j]
dp[i][j] = grid[i][j] + min( dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1] )
clamping the two diagonal reads at the edges.
The space is the reason this problem is here. Row i depends only on row
i - 1, so two rows are enough and the table never needs to exist in full. That
turns O(r * c) space into O(c), and it is the standard rolling-array move for
any grid DP whose dependencies reach back exactly one row.
Note the rolling version must write into a SEPARATE row rather than overwrite in
place, because dp[i][j] reads dp[i-1][j+1], a column to the right that an
in-place left-to-right sweep would already have replaced.
Constraints - `1 ≤ r, c ≤ 300` - `-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 of any fall from the top row to the bottom row.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.