# 1289. Minimum Falling Path Sum II
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/minimum-falling-path-sum-ii/
## 思路
此题和[0256. Paint House](https://hackmd.io/IH85BfuSQAyObMZxbUAcPQ)本质上一模一样：每一行表示给一座房子涂颜色，每一列表示颜色的种类，```arr[i][j]```就是给某座房子涂某种油漆的代价，要求相邻的两座房子不能颜色相同

我们每次找到dp[i-1]里面的最小值，大部分dp[i][j]可以从min(dp[i-1])+grid[i][j]得到，除非j和上一行最小值的column数是一样的，这时候我们会找次小值
## Code

class Solution {
public int minFallingPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] dp = new int[n];

for(int i=0; i<n; i++){
dp[i] = grid[0][i];
}

for(int i=1; i<m; i++){
int[] temp = dp.clone();
Arrays.sort(temp);
int minIdx = -1;
for(int j=0; j<n; j++) if(dp[j]==temp[0]) minIdx = j;
for(int j=0; j<n; j++){
if(j!=minIdx){
dp[j] = temp[0]+grid[i][j];
}
else dp[j] = temp[1]+grid[i][j];
}
}

int min = Integer.MAX_VALUE;
for(int i=0; i<n; i++){
min = Math.min(min, dp[i]);
}
return min;
}
}