Leetcode: Minimum Falling Path Sum

Minimum Falling Path Sum


<a href=”https://github.com/dennyzhang/code.dennyzhang.com/tree/master/problems/minimum-falling-path-sum“><img align=”right” width=”200″ height=”183″ src=”github.png” /></a>

Similar Problems:


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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// Blog link: https://code.dennyzhang.com/minimum-falling-path-sum
// Basic Ideas: dynamic programming
//    1 2 3
//    4 5 6
//    7 8 9
// Complexity: Time O(n*m), Space O(n)
func minFallingPathSum(A [][]int) int {
    dp := make([]int, len(A[0]))
    l := make([]int, len(A[0]))
    for j:=0; j<len(dp); j++ {
        dp[j] = A[0][j]
    }
    for i:=1; i<len(A); i++ {
        for j:=0; j<len(dp); j++ {
            l[j] = dp[j]+A[i][j]
            if j!=0 && l[j] > dp[j-1]+A[i][j] {
                l[j] = dp[j-1]+A[i][j]
            }
            if j!=len(dp)-1 && l[j]>dp[j+1]+A[i][j] {
                l[j] = dp[j+1]+A[i][j]
            }
        }
        for j:=0; j<len(dp); j++ {
            dp[j]= l[j]
        }
    }
    res := 1<<32-1
    for j:=0; j<len(dp); j++ {
        if res > dp[j] { res = dp[j] }
    }
    return res
}

<div style=”overflow: hidden;”>

<div style=”float: left; padding: 5px”> <a href=”https://www.linkedin.com/in/dennyzhang001“><img src=”linkedin.png” alt=”linkedin” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://github.com/dennyzhang“><img src=”github.png” alt=”github” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://www.dennyzhang.com/slack” target=”_blank” rel=”nofollow”><img src=”slack.png” alt=”slack”/></a></div>

</div>


Share It, If You Like It.

Leave a Reply

Your email address will not be published.