hardDynamic Programming 2DPure DSA~40 min
Minimum Falling Path With No Repeated Column
A drone descends an n x n cost grid one row per step. It may not land in the same column on two consecutive rows. Minimize the total cost of a full top-to-bottom descent.
Problem
Given an n x n integer matrix, choose one cell from each row such that no two cells in adjacent rows are in the same column, minimizing the sum of chosen cells. Return that minimum sum.
Input
An n x n integer matrix.
Output
An integer: the minimum non-zero-shift falling path sum.
Constraints
- 1 <= n <= 200
- -99 <= matrix[i][j] <= 99
- Adjacent-row picks must be in different columns.
Examples
Example 1
Input
matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output
13
1 (row0) + 5 (row1) + 7 (row2) = 13, with all columns differing between adjacent rows.
Example 2
Input
matrix = [[7]]
Output
7
Single cell.