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.
1public class Solution {
2 public int MinFallingPathSum(int[][] matrix) {
3 int n = matrix.Length;
4 for (int i = n - 2; i >= 0; i--) {
5 for (int j = 0; j < n; j++) {
6 int best = matrix[i + 1][j];
7 if (j > 0) best = Math.Min(best, matrix[i + 1][j - 1]);
8 if (j < n - 1) best = Math.Min(best, matrix[i + 1][j + 1]);
9 matrix[i][j] += best;
10 }
11 }
12 int minSum = int.MaxValue;
13 foreach (int val in matrix[0]) {
14 minSum = Math.Min(minSum, val);
15 }
16 return minSum;
17 }
18}
19C# solution exemplifies in-place dynamic programming for calculating falling path sums and uses a loop to find the minimum sum 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.
1#include <algorithm>
using namespace std;
vector<vector<int>> memo;
int dfs(vector<vector<int>>& matrix, int row, int col) {
int n = matrix.size();
if (row == n) return 0;
if (memo[row][col] != INT_MAX) return memo[row][col];
int res = matrix[row][col] + dfs(matrix, row + 1, col);
if (col > 0) res = min(res, matrix[row][col] + dfs(matrix, row + 1, col - 1));
if (col < n - 1) res = min(res, matrix[row][col] + dfs(matrix, row + 1, col + 1));
return memo[row][col] = res;
}
int minFallingPathSum(vector<vector<int>>& matrix) {
int n = matrix.size();
memo.assign(n, vector<int>(n, INT_MAX));
int minSum = INT_MAX;
for (int col = 0; col < n; ++col) {
minSum = min(minSum, dfs(matrix, 0, col));
}
return minSum;
}
The C++ implementation utilizes memoization to store already computed sums, reducing the number of dynamic calculations and speeding up the process by tracking results in a matrix.