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 <vector>
2#include <algorithm>
3using namespace std;
4
5int minFallingPathSum(vector<vector<int>>& matrix) {
6 int n = matrix.size();
7 for (int i = n - 2; i >= 0; i--) {
8 for (int j = 0; j < n; j++) {
9 int mn = matrix[i + 1][j];
10 if (j > 0) mn = min(mn, matrix[i + 1][j - 1]);
11 if (j < n - 1) mn = min(mn, matrix[i + 1][j + 1]);
12 matrix[i][j] += mn;
13 }
14 }
15 return *min_element(matrix[0].begin(), matrix[0].end());
16}
17This C++ solution updates the matrix from the bottom to the top, using an in-place approach to accumulate the minimal path sums, then returns the smallest total from the top 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
In the C solution, a recursive function with memoization is used to compute the minimum falling path sum starting from every element in the first row. The memo table avoids recalculation of already known results.