# 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=”” /></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;”>