Cheapest Falling Route
Medium2-D Dynamic Programming
Problem
A square board board of size n × n holds integers (possibly negative). A token is dropped onto any cell of the top row and falls to the bottom row, one row per step. From column j it may land in column j - 1, j or j + 1 of the next row, as long as that column exists.
The cost of a fall is the sum of the cells the token touches, one per row. Return the minimum cost over all possible falls.
Example 1
- Input:
- board = [[4, 2, 7], [3, 8, 1], [6, 5, 9]]
- Output:
- 8
2 → 1 → 5: start in the middle, drift right, then back to the middle.
Example 2
- Input:
- board = [[-5]]
- Output:
- -5
Constraints
- 1 ≤ n ≤ 200
- -100 ≤ board[r][c] ≤ 100
Hint
Show the first hint
Define the cheapest cost of a fall that ends on cell (r, c), for every cell.
Walkthrough
How to approach it
01Clarify before coding
- Can the token start anywhere in the top row? Yes, and it may end anywhere in the bottom row.
- Can values be negative? Yes; the DP does not care, since every fall has exactly n cells.
- What happens at the edges? Column 0 has only two possible parents (0 and 1), and so does column n - 1.
02Brute force
From each top cell, recursively try all three moves per row and keep the smallest total.
Cost: O(n · 3^n) time: for n = 200 that is beyond astronomical.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.