This 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.
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.
1class Solution:
2 def minFallingPathSum(self, grid):
3 n = len(grid)
4 dp = [row[:] for row in grid]
5 for i in range(1, n):
6 for j in range(n):
7 minPrev = min(dp[i-1][k] for k in range(n) if k != j)
8 dp[i][j] = grid[i][j] + minPrev
9 return min(dp[-1])In Python, we copy the grid into a new DP matrix, iteratively calculating the minimum path sums while disallowing consecutive selection from the same column.
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).
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.
1public class Solution {
2 public int MinFallingPathSum(int[][] grid) {
3 int n = grid.Length;
4 int[] prev = (int[])grid[0].Clone();
5 int[] curr = new int[n];
6 for (int i = 1; i < n; i++) {
7 for (int j = 0; j < n; j++) {
8 int minPrev = Int32.MaxValue;
9 for (int k = 0; k < n; k++) {
10 if (k != j) minPrev = Math.Min(minPrev, prev[k]);
11 }
12 curr[j] = grid[i][j] + minPrev;
13 }
14 Array.Copy(curr, prev, n);
15 }
16 return curr.Min();
17 }
18}This C# approach is built to handle fall paths with minimum space, adjusting from a matrix form to a dual-array setup, tracking and calculating the smallest shift path values between rows through curr and prev arrays.