LeetCode. One question of the day: offer II 091 Paint the house (DP problem)

The finger of the sword Offer II 091. Paint the house

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
 

Solution:

• Here is the obvious dynamic programming problem , What we require is the minimum cost of painting all the houses , And we know , You give No i When painting a house, it is only related to the color of the previous house next to it , So it can be seen that the change of state lies in the color of two adjacent houses .
• So we might as well set dp[i][j] Before painting i Houses , And the first i Paint a house j The minimum cost of color , So we just need to get dp[n-1][0],dp[n-1][1],dp[n-1][2] The minimum value in is enough , Get painted 0~n-1 Houses , And the last house is painted red , Blue , The minimum cost of green , Take min.

So clearly , According to our agreement that adjacent houses cannot be painted with the same color , You can cycle through the house , Transfer the painting state every time , Take the minimum cost every time .

Code:

class Solution {
    
    public int minCost(int[][] costs) {
    
        int len = costs.length;
        int[][] dp = new int[len][3];
        dp[0][0] = costs[0][0];
        dp[0][1] = costs[0][1];
        dp[0][2] = costs[0][2];
        for(int i=1;i<len;i++){
    
            dp[i][0] = Math.min(dp[i-1][1],dp[i-1][2]) + costs[i][0];
            dp[i][1] = Math.min(dp[i-1][0],dp[i-1][2]) + costs[i][1];
            dp[i][2] = Math.min(dp[i-1][1],dp[i-1][0]) + costs[i][2];
        }
        return Math.min(dp[len-1][0],Math.min(dp[len-1][1],dp[len-1][2]));
    }
}