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.
1public class Solution {
2 public int MinFallingPathSum(int[][] grid) {
3 int n = grid.Length;
4 int[][] dp = new int[n][];
5 for (int i = 0; i < n; i++) {
6 dp[i] = new int[n];
7 Array.Copy(grid[i], dp[i], n);
8 }
9 for (int i = 1; i < n; i++) {
10 for (int j = 0; j < n; j++) {
11 int minPrev = Int32.MaxValue;
12 for (int k = 0; k < n; k++) {
13 if (k != j) minPrev = Math.Min(minPrev, dp[i-1][k]);
14 }
15 dp[i][j] = grid[i][j] + minPrev;
16 }
17 }
18 return dp[n-1].Min();
19 }
20}This C# implementation constructs a DP replica of the input grid to compute path sums, bypassing direct selections from the prior row's 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.
1var minFallingPathSum = function(grid) {
2 const n = grid.length;
3 let prev = [...grid[0]];
4 for (let i = 1; i < n; i++) {
5 const curr = new Array(n).fill(Infinity);
6 for (let j = 0; j < n; j++) {
7 for (let k = 0; k < n; k++) {
8 if (k !== j) {
9 curr[j] = Math.min(curr[j], grid[i][j] + prev[k]);
10 }
11 }
12 }
13 prev = curr;
14 }
15 return Math.min(...prev);
16};Javascript dynamically updates two 1D arrays to compute minimum falling path sums. Switching from one to another per current and previous status limits memory usage while covering optimal path steps.