# 931. Minimum Falling Path Sum

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`

``````class Solution {
public:
int minFallingPathSum(vector<vector<int>>& A) {
if (A.size() == 1) return A[0][0];
int n = A.size(), res = INT_MAX;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int pre = A[i - 1][j];
if (j > 0) pre = min(pre, A[i - 1][j - 1]);
if (j < n - 1) pre = min(pre, A[i - 1][j + 1]);
A[i][j] += pre;
if (i == n - 1) res = min(res, A[i][j]);
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/931

Minimum Falling Path Sum II

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

https://leetcode.com/problems/minimum-falling-path-sum/discuss/186666/C%2B%2BJava-4-lines-DP

https://leetcode.com/problems/minimum-falling-path-sum/discuss/186689/Java-DP-solution-with-graph-illustrated-explanations

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation