Minimum Dropping Path Sum
You are given a two-dimensional list of integers matrix. Return the minimum sum you can get by taking a number in each row with the constraint that any row-adjacent numbers cannot be in the same column.
Constraints
1 ≤ n ≤ 250wherenis the number of rows inmatrix2 ≤ m ≤ 250wheremis the number of columns inmatrix
https://binarysearch.com/problems/Minimum-Dropping-Path-Sum
ExamplesPermalink
Example 1Permalink
Input
- matrix =
[[ 4, 5,-2],
[ 2, 6, 1],
[ 3, 1, 2]]
Output
- answer =
1
Explanation
We can take -2 from the first row, 2 from the second row, and 1 from the last row.
Example 2Permalink
Input
- matrix =
[[ 3, 0, 3],
[ 2, 1, 3],
[-2, 3, 0]]
Output
- answer =
1
Explanation
We can take 0 from the first row, 3 from the second row, and -2 from the last row.
SolutionPermalink
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| int solve(vector<vector<int>> &matrix) | |
| { | |
| int nRows = matrix.size(); | |
| int nCols = matrix[0].size(); | |
| for (int r = 1; r < nRows; r++) | |
| { | |
| int prevMin = INT_MAX, prevSecondMin = INT_MAX; | |
| // find min and secondMin of previous row | |
| for (int c = 0; c < nCols; c++) | |
| { | |
| if (matrix[r - 1][c] < prevMin) | |
| { | |
| prevSecondMin = prevMin; | |
| prevMin = matrix[r - 1][c]; | |
| } | |
| else if (matrix[r - 1][c] < prevSecondMin) | |
| { | |
| prevSecondMin = matrix[r - 1][c]; | |
| } | |
| } | |
| // at current row, add either `prevMin` or `prevSecondMin` | |
| for (int c = 0; c < nCols; c++) | |
| { | |
| if (matrix[r - 1][c] == prevMin) | |
| matrix[r][c] += prevSecondMin; | |
| else | |
| matrix[r][c] += prevMin; | |
| } | |
| } | |
| return *min_element(matrix[nRows - 1].begin(), matrix[nRows - 1].end()); | |
| } |
Leave a comment