[dynamic planning] Jianzhi offer II 091 Paint the house

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 .
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 .

Ideas ： Solve this problem , At first, I mistakenly used greedy practices , Later, I found that if every time I was greedy , Results take the minimum value of each room , Wrong result

The correct solution ： Dynamic programming
step1、dp[i][j] Express [0,i-1] A house ,i-1 Apply color between j, The minimum cost is dp[i][j]

step2、 The recursive formula
dp[i][j] = min(dp[i-1][m]) + costs[i-1][j], requirement m != j
step3、 initialization

step4、 Recursive order , From left to right

step5、 For example

Code implementation

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