Minimum Falling Path Sum - DP Solution
Very similar problem to the previous post, with a similar DP solution: https://leetcode.com/problems/minimum-falling-path-sum/description/
Same hints as before: minimum (or maximum) ask, highly exponential brute-force solution. Idea here is to also have a table with the best solution up to cell (i,j) and construct the solution all the way to the last row, then do a pass in the last row looking for the min. I could have used only one row (O(N)-space) for storage, but the solution below uses O(N^2)-space with an O(N^2)-time complexity (remember that N^2 here is "linear" since this is the number of cells we have). Thanks! Marcelo
Given a square array of integers
A, we want the minimum sum of a falling path through A.
A falling path starts at any element in the first row, and chooses one element from each row. The next row's choice must be in a column that is different from the previous row's column by at most one.
Example 1:
Input: [[1,2,3],[4,5,6],[7,8,9]] Output: 12 Explanation: The possible falling paths are:
[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9][2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9][3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
The falling path with the smallest sum is
[1,4,7], so the answer is 12.
Note:
1 <= A.length == A[0].length <= 100-100 <= A[i][j] <= 100
Same hints as before: minimum (or maximum) ask, highly exponential brute-force solution. Idea here is to also have a table with the best solution up to cell (i,j) and construct the solution all the way to the last row, then do a pass in the last row looking for the min. I could have used only one row (O(N)-space) for storage, but the solution below uses O(N^2)-space with an O(N^2)-time complexity (remember that N^2 here is "linear" since this is the number of cells we have). Thanks! Marcelo
public class Solution
{
public int MinFallingPathSum(int[][] A)
{
if (A == null) return 0;
int N = A.GetLength(0);
int[][] dp = new int[N][];
//Base
dp[0] = new int[N];
for (int c = 0; c < N; c++) dp[0][c] = A[0][c];
//Construction
for (int r = 1; r < N; r++)
{
dp[r] = new int[N];
for (int c = 0; c < N; c++)
{
dp[r][c] = Int32.MaxValue;
dp[r][c] = (c - 1 >= 0) ? Math.Min(dp[r][c], dp[r - 1][c - 1]) : dp[r][c];
dp[r][c] = Math.Min(dp[r][c], dp[r - 1][c]);
dp[r][c] = (c + 1 < N) ? Math.Min(dp[r][c], dp[r - 1][c + 1]) : dp[r][c];
dp[r][c] += A[r][c];
}
}
int result = Int32.MaxValue;
for (int c = 0; c < N; c++) result = Math.Min(result, dp[N - 1][c]);
return result;
}
}
Classic! The only thing that can be improved is the space usage, since we only need a previous row and not the entire table. As it's often the case with Rust though, solutions using full table and only a single row both take 0ms, so it's hard to quantify the benefit...
ReplyDeleteimpl Solution {
pub fn min_falling_path_sum(a: Vec>) -> i32 {
let mut prev: Vec = a[0].clone();
let mut curr: Vec = vec![0; a[0].len()];
for i in 1..a.len() {
for j in 0..a[i].len() {
let mut sum_so_far = prev[j];
if j > 0 {
sum_so_far = std::cmp::min(sum_so_far, prev[j-1]);
}
if j < a[i].len() - 1 {
sum_so_far = std::cmp::min(sum_so_far, prev[j+1]);
}
curr[j] = a[i][j] + sum_so_far;
}
std::mem::swap(&mut curr, &mut prev);
}
*prev.iter().min().unwrap()
}
}
https://gist.github.com/ttsugriy/0e4c62cfe070ddc2d8dd3108078335c1