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

因此状态转移方程也很类似：

相比与传统的走迷宫的DP，此题不确定的是“最小权和路径”的结束点的具体位置。所以最后的答案是在最后一行的```dp[m-1][j]```中扫描一个，找最小的那个。
## Code

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;
}
}