# 0256. Paint House
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/paint-house/
## 思路
和[1289. Minimum Falling Path Sum II](https://hackmd.io/3trxUuWbQnybTTNZTPwjuw)一毛一样
每一行表示给一座房子涂颜色，每一列表示颜色的种类，```arr[i][j]```就是给某座房子涂某种油漆的代价，要求相邻的两座房子不能颜色相同

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

class Solution {
public int minCost(int[][] costs) {
int m = costs.length, n = costs[0].length;
int[] dp = new int[n];
for(int i=0; i<n; i++){
dp[i] = costs[0][i];
}
for(int i=1; i<m; i++){
//find min, second min and minIdx
int minIdx = -1, min = Integer.MAX_VALUE, secondMin = Integer.MAX_VALUE;
for(int j=0; j<n; j++){
if(dp[j]<min){
secondMin = min;
min = dp[j];
minIdx = j;
}
else if(dp[j]<secondMin) secondMin = dp[j];
}
//build dp array
for(int j=0; j<n; j++){
if(j!=minIdx) dp[j] = min+costs[i][j];
else dp[j] = secondMin+costs[i][j];
}
}
int ans = Integer.MAX_VALUE;
for(int i=0; i<n; i++){
ans = Math.min(ans, dp[i]);
}
return ans;
}
}