当前位置：网站首页>Sword finger offer special breakthrough version 91. Painting the house

Sword finger offer special breakthrough version 91. Painting the house

2022-04-22 03:04:00 【Catch Lulu, little cute (๑ • • ๑)】

Topic link

Ideas

  • set up dp[i][j] It's No i Paint the first house j The total cost of each color , So naturally dp[i][j] = min{dp[i-1][(j+1)%3],dp[i-1][(j+2)%3]} + cost[i]
  • in other words dp[i][j] The minimum value of the other two colors for the previous house should be added to the color of this house j Cost 
class Solution {
    
    public int minCost(int[][] costs) {
    
        int[][] dp = new int[2][3];
        System.arraycopy(costs[0], 0, dp[0], 0, 3);

        for (int i = 1; i < costs.length; i++) {
    
            for (int j = 0; j < 3; j++) {
    
                dp[i % 2][j] = Math.min(dp[(i - 1) % 2][(j + 1) % 3], dp[(i - 1) % 2][(j + 2) % 3]) + costs[i][j];
            }
        }
        int index = (costs.length - 1) % 2;
        return Math.min(Math.min(dp[index][0], dp[index][1]), dp[index][2]);
    }
}

版权声明
本文为[Catch Lulu, little cute (๑ • • ๑)]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/04/202204220300400758.html

边栏推荐

猜你喜欢

随机推荐