LeetCode 931. Minimum Falling Path Sum

Link:- https://leetcode.com/problems/minimum-falling-path-sum/

Summary:

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.

For Example:
Input:

[[1,2,3],[4,5,6],[7,8,9]]

Output:
12

Logic:

Given array A with row ->n and column ->n

now create matrix say ans[n][m]

copy first row of A into ans

i.e ans[0] = A[0]

Why?

since we can start from any column in first row

now for rest of the row and column say i and j (1<=i<n, 0<=j<m)

ans[i][j] = A[i][j] + min(ans[i][j-1], ans[i-1][j-1], ans[i-1][j+1]

return min(ans[n-1])

i.e minimum of all values in last row

Why?

because we can end at any column of last row.

To View My Solution:

https://github.com/shivam04/codes/blob/master/leetcode/minimum-falling-path-sum.cpp