Sponsored
Sponsored
Using a dynamic programming matrix, you can start from the second-last row of the matrix and calculate the minimum path sum by traversing through possible paths (directly below, diagonally left, and diagonally right). Update the matrix in-place to use constant space.
Time Complexity: O(n^2) because each element is visited once.
Space Complexity: O(1) since the computations are done in place.
1#include <stdio.h>
2#include <limits.h>
3
4int minFallingPathSum(int** matrix, int matrixSize, int* matrixColSize) {
5 for (int row = matrixSize - 2; row >= 0; row--) {
6 for (int col = 0; col < matrixColSize[row]; col++) {
7 int best = matrix[row + 1][col];
8 if (col > 0) {
9 best = (best < matrix[row + 1][col - 1]) ? best : matrix[row + 1][col - 1];
10 }
11 if (col < matrixColSize[row + 1] - 1) {
12 best = (best < matrix[row + 1][col + 1]) ? best : matrix[row + 1][col + 1];
13 }
14 matrix[row][col] += best;
15 }
16 }
17 int minSum = INT_MAX;
18 for (int i = 0; i < matrixColSize[0]; i++) {
19 if(matrix[0][i] < minSum) {
20 minSum = matrix[0][i];
21 }
22 }
23 return minSum;
24}
25In the C solution, we iterate from the second-last row to the first row, and for each element, we compute the minimum sum from possible paths below. We update the original matrix with these minimum values and finally compute the minimum value in the first row.
For this approach, we use recursion with memoization to explore paths starting from the first row to the last row. We store intermediate results to avoid redundant calculations.
Time Complexity: O(n^2) due to memoization reducing redundant calculations.
Space Complexity: O(n^2) due to the memoization table.
1public class Solution {
private int[][] memo;
public int MinFallingPathSum(int[][] matrix) {
int n = matrix.Length;
memo = new int[n][];
for (int i = 0; i < n; i++) {
memo[i] = new int[n];
for (int j = 0; j < n; j++) {
memo[i][j] = int.MaxValue;
}
}
int minSum = int.MaxValue;
for (int col = 0; col < n; col++) {
minSum = Math.Min(minSum, Dfs(matrix, 0, col));
}
return minSum;
}
private int Dfs(int[][] matrix, int row, int col) {
int n = matrix.Length;
if (row == n) return 0;
if (memo[row][col] != int.MaxValue) return memo[row][col];
int res = matrix[row][col] + Dfs(matrix, row + 1, col);
if (col > 0) res = Math.Min(res, matrix[row][col] + Dfs(matrix, row + 1, col - 1));
if (col < n - 1) res = Math.Min(res, matrix[row][col] + Dfs(matrix, row + 1, col + 1));
memo[row][col] = res;
return res;
}
}The C# solution explores the use of memoization to optimize recursive calculations and cache intermediate results, ensuring no repeated computations occur.