Algorithm --- paint the house (kotlin)

subject

If there is a row of houses , common n individual , Every house can be painted red 、 One of the three colors blue or green , You need to paint all the houses and make the two adjacent houses not the same color .

Of course , Because the prices of different colors of paint on the market are different , So the cost of painting the house in different colors is different . The cost of painting each house in a different color is one n x 3 Positive integer matrix of costs To represent the .

for example ,costs[0][0] It means the first one 0 The cost of painting the house red ;costs[1][2] It means the first one 1 The cost of painting the house green , And so on .

Please calculate the minimum cost of painting all the houses .

Example 1：

Input : costs = [[17,2,17],[16,16,5],[14,3,19]]
Output : 10
explain : take 0 No. 1 house painted blue ,1 No. 1 house painted green ,2 No. 1 house painted blue .
Minimum cost : 2 + 5 + 3 = 10.
Example 2：

Input : costs = [[7,6,2]]
Output : 2

Tips :

costs.length == n
costs[i].length == 3
1 <= n <= 100
1 <= costs[i][j] <= 20

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/JEj789
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Solutions

resolvent

    fun minCost2(costs: Array<IntArray>): Int {
    

        val n = costs.size
        val dp = Array(n) {
     Array(3) {
     0 } }
        costs[0].forEachIndexed {
     index, int ->
            dp[0][index] = int
        }
        for (i in 1 until n){
    
            for (j in 0..2){
    
                dp[i][j] = dp[i - 1][(j + 1) % 3].coerceAtMost(dp[i - 1][(j + 2) % 3]) + costs[i][j]
            }
        }
        return Arrays.stream(dp[n - 1]).min {
     o1: Int, o2: Int -> o1 - o2 }.get()
    }

summary

1. Think more about using for loop instead of copy Code
For example, there are only 3 Number How to get the left and right arrays

2.dp Arrays can also be binary arrays Can be changed according to needs