---
# System prepended metadata

title: 0931. Minimum Falling Path Sum
tags: [Leetcode, Dynamic Programming, Medium]

---

# 0931. Minimum Falling Path Sum
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/minimum-falling-path-sum/
## 思路
最传统的走迷宫的DP题，是问从左上角走到右下角的最小权和路径，每次走只能向右或者向下。此题本质上一样，是问从第一行到最后一行的最小权和路径，每次只能朝是那个方向（左下，正下，右下）。

因此状态转移方程也很类似：
```dp[i][j] = min (dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]) + A[i][j];```

相比与传统的走迷宫的DP，此题不确定的是“最小权和路径”的结束点的具体位置。所以最后的答案是在最后一行的```dp[m-1][j]```中扫描一个，找最小的那个。
## Code
```java=
class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix[0].length;
        int[] dp = new int[n];
        
        for(int i=0; i<n; i++) dp[i] = matrix[0][i];
        for(int i=1; i<n; i++){
            int[] temp = new int[n];
            for(int j=0; j<n; j++){
                int next = matrix[i][j];
                if(n==1) temp[j] = next+dp[j];
                if(j==0) temp[j] = Math.min(dp[j], dp[j+1])+next;
                else if(j==n-1) temp[j] = Math.min(dp[j], dp[j-1])+next;
                else temp[j] = Math.min(dp[j], Math.min(dp[j+1], dp[j-1]))+next;
            }
            dp = temp;
        }
        
        int ans = Integer.MAX_VALUE;
        for(int i=0; i<n; i++){
            ans = Math.min(ans, dp[i]);
        }
        return ans;
    }
}
```