Show problems as
Classic problem #931MediumArrayDynamic ProgrammingMatrix

Minimum Falling Path Sum

Real-world version: Least Strain Down the Wall
Tracked in this browser only
Read Minimum Falling Path Sum on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstInterval/Range DP · Dynamic Programming, animated step by step

A training wall is bolted with holds in a square grid of n rows and n columns. holds[r][c] is the strain, in newtons, that using the hold in row r and column c costs a climber. Some holds are shaped as rests and carry a negative strain, because the climber recovers on them.

A descent uses exactly one hold from every row. It may begin at any hold in row 0 and finish at any hold in row n - 1. From a hold in column c, the only holds the climber can reach in the next row are those in columns c - 1, c and c + 1, and only where that column exists on the wall.

The cost of a descent is the total strain of the holds it uses. Return the smallest cost any descent can have.

Examples

Example 1

Input
holds = [[2, 9, 9], [9, 1, 9], [3, 9, 9]]
Output
6

Starting at column 0 in the top row costs 2, then column 1 in the middle row costs 1, then column 0 in the bottom row costs 3, for 6 newtons in total. Each step moves at most one column sideways.

Example 2

Input
holds = [[1, 100, 100], [100, 100, 2], [100, 100, 3]]
Output
104

Taking column 0 at the top costs 1, column 1 in the middle costs 100, and column 2 at the bottom costs 3, which is 104 newtons for a descent that shifts one column right at each step.

Example 3

Input
holds = [[-7]]
Output
-7

The wall has a single hold, and using it is the only descent there is.

Example 4

Input
holds = [[-100, -100], [-100, -100]]
Output
-200

Every hold is a rest worth -100, so any descent takes two of them and totals -200.

Example 5

Input
holds = [[0, 1, 100], [100, 0, 1], [1, 100, 0]]
Output
0

Taking column 0 at the top, column 1 in the middle and column 2 at the bottom costs 0 + 0 + 0 = 0, and each of those steps moves one column to the right.

Constraints

  • n == holds.length == holds[i].length
  • 1 <= n <= 100
  • -100 <= holds[i][j] <= 100

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_falling_path_sum(holds: list[list[int]]) -> int:
Java
public int minFallingPathSum(int[][] holds)

More on the same topics