---
# System prepended metadata

title: 0256. Paint House
tags: [Leetcode, Dynamic Programming, Medium]

---

# 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)一毛一样
![](https://i.imgur.com/QZriSOk.png)
每一行表示给一座房子涂颜色，每一列表示颜色的种类，```arr[i][j]```就是给某座房子涂某种油漆的代价，要求相邻的两座房子不能颜色相同
```dp[i][j]```表示从第一行走到```grid[i][j]```的最小权重路径
我们每次找到dp[i-1]里面的最小值，大部分dp[i][j]可以从min(dp[i-1])+grid[i][j]得到，除非j和上一行最小值的column数是一样的，这时候我们会找次小值
## Code
```java=
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;
    }
}
```