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.
1var minFallingPathSum = function(grid) {
2 const n = grid.length;
3 const dp = Array.from({ length: n }, (v, i) => [...grid[i]]);
4 for (let i = 1; i < n; i++) {
5 for (let j = 0; j < n; j++) {
6 let minPrev = Infinity;
7 for (let k = 0; k < n; k++) {
8 if (k !== j) minPrev = Math.min(minPrev, dp[i-1][k]);
9 }
10 dp[i][j] = grid[i][j] + minPrev;
11 }
12 }
13 return Math.min(...dp[n-1]);
14};JavaScript uses an approach similar to other languages, a 2D array tracks cumulative path sums, while ensuring column shift, to find the minimum ending path value.
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.
1#include <limits.h>
2#include <string.h>
3int minFallingPathSum(int** grid, int gridSize, int* gridColSize) {
4 int n = gridSize;
5 int prev[n], curr[n];
6 memcpy(prev, grid[0], sizeof(int) * n);
7 for (int i = 1; i < n; i++) {
8 for (int j = 0; j < n; j++) {
9 int minPrev = INT_MAX;
10 for (int k = 0; k < n; k++) {
11 if (k != j) minPrev = fmin(minPrev, prev[k]);
12 }
13 curr[j] = grid[i][j] + minPrev;
14 }
15 memcpy(prev, curr, sizeof(int) * n);
16 }
17 int minPath = INT_MAX;
18 for (int j = 0; j < n; j++) minPath = fmin(minPath, prev[j]);
19 return minPath;
20}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.