【动态规划】剑指 Offer II 091. 粉刷房子

剑指 Offer II 091. 粉刷房子

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
请计算出粉刷完所有房子最少的花费成本。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/JEj789
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：解决这道题目，一开始自己错误的使用贪心做法，后来发现如果每次贪心，结果取每个房间的最小值，出现错误结果

正确解法：动态规划
step1、dp[i][j] 表示 [0，i-1]间房子，i-1 间使用涂色 j，最小成本是 dp[i][j]

step2、递推公式
dp[i][j] = min(dp[i-1][m]) + costs[i-1][j], 要求m != j
step3、初始化

step4、递推顺序，从左到右

step5、举例子

代码实现

 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]);
    }