Given an n x n integer matrix grid, return the minimum sum of a falling path with non-zero shifts.
A falling path with non-zero shifts is a choice of exactly one element from each row of grid such that no two elements chosen in adjacent rows are in the same column.
Example 1:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]] Output: 13 Explanation: The possible falling paths are: [1,5,9], [1,5,7], [1,6,7], [1,6,8], [2,4,8], [2,4,9], [2,6,7], [2,6,8], [3,4,8], [3,4,9], [3,5,7], [3,5,9] The falling path with the smallest sum is [1,5,7], so the answer is 13.
Example 2:
Input: grid = [[7]] Output: 7
Constraints:
n == grid.length == grid[i].length1 <= n <= 200-99 <= grid[i][j] <= 99This approach uses dynamic programming to keep track of the minimum sum at each position and makes sure no two consecutive rows select a value from the same column. We use a 2D DP array where dp[i][j] represents the minimum path sum to reach element grid[i][j]. Expand on each row by calculating potential path sums from the previous row using existing minimum path sums stored in the DP table.
This C solution uses an integer array dp to store the minimum path sums, ensuring no same column values from contiguous rows are included by looping to check all columns except the current column.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^3) where n is the number of rows or columns in the grid.
Space Complexity: O(n^2) for the auxiliary DP array.
This approach enhances space efficiency by using two 1D arrays to store only the last row and the current row values of the DP computations. At each step, we compute the minimum path and store it, minimizing space usage to O(n) instead of O(n^2).
The C solution employs two arrays, prev and curr, to alternate between rows of calculations, minimizing memory use while maintaining previous state information for each row during traversal.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^3) because Min operation checks all columns for each column in each row.
Space Complexity: O(n) using two 1D arrays for storing current and previous row states in DP.
| Approach | Complexity |
|---|---|
| Dynamic Programming with State Tracking | Time Complexity: O(n^3) where n is the number of rows or columns in the grid. |
| Dynamic Programming with Space Optimization | Time Complexity: O(n^3) because Min operation checks all columns for each column in each row. |
DP 12. Minimum/Maximum Falling Path Sum | Variable Starting and Ending Points | DP on Grids • take U forward • 270,793 views views
Watch 9 more video solutions →Practice Minimum Falling Path Sum II with our built-in code editor and test cases.
Practice on FleetCode