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/

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. 1 <= A.length == A[0].length <= 100
  2. -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! Boris


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;
 }
}

Comments

  1. TarasJanuary 4, 2019 at 6:17 PM

    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...

    impl 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

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more