Leetcode Problem 931. Minimum Falling Path Sum

931. Minimum Falling Path Sum

Leetcode Solutions

Bottom-Up Dynamic Programming (Tabulation)

  1. Initialize a 2D array dp with the same dimensions as matrix and fill the last row of dp with the values of the last row of matrix.
  2. Iterate over the matrix from the second last row to the first row (bottom to top).
  3. For each cell (row, col) in the current row, calculate the minimum sum of the falling path by considering the values directly below and the diagonally left and right cells in the dp array.
  4. Update the dp[row][col] with the calculated minimum sum.
  5. After filling the dp table, the first row of dp will contain the minimum falling path sums starting from each cell in the first row of matrix.
  6. Return the minimum value from the first row of dp as the result.
UML Thumbnail

Brute Force Using Depth First Search

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...