Leetcode - 256&265. 粉刷房子

class Solution {

    /**
     * 已知条件1：数组[r, b, g]表示将某个房子粉刷成红/蓝/绿色时所需的价格
     * 已知条件2：有一排房子，共n个，其粉刷价格用一个(n * 3)的矩阵来表示，相邻房子不能粉刷成相同颜色
     * 题目要求：现对这些房子进行粉刷，问最小的花费是多少
     */

    public int minCost(int[][] costs) {
        if(costs == null || costs.length == 0)
            return 0;

        //使用动态规划：假设第0到第(i - 1)个房子都已经被粉刷好了，现要粉刷第i个房子
        
        //不妨假设将第i个房子粉刷成红色，该房子的花费为costs[i][0]
        //此时，需要看将第(i - 1)个房子粉刷成蓝色或绿色时前(i - 1)个房子的总花费，取其较小值preMinBG
        //那么，将第0到第i个房子粉刷好，并且第i个房子为红色的最小花费是(costs[i][0] + preMinBG)
        
        //将第i个房子刷成蓝/绿色时，前i个房子的最小花费是也可以用类似的方法求得

        for(int i = 1; i < costs.length; i++){
            int[] thisHouse = costs[i], preHouse = costs[i - 1];
            thisHouse[0] += Math.min(preHouse[1], preHouse[2]);
            thisHouse[1] += Math.min(preHouse[0], preHouse[2]);
            thisHouse[2] += Math.min(preHouse[0], preHouse[1]);
        }

        //返回最后一个数组中的最小元素即可
        int[] lastHouse = costs[costs.length - 1];
        return Math.min(Math.min(lastHouse[0], lastHouse[1]), lastHouse[2]);
    }


    /**
     * 进阶（题目二）：现在颜色不止红蓝绿三种，而是有k种颜色可选，问粉刷n个房子的最小花费；要求时间复杂度O(nk)
     */
    
    public int minCostII(int[][] costs) {
        if(costs == null || costs.length == 0)
            return 0;

        //使用动态规划：假设第0到第(i - 1)个房子都已经被粉刷好了，现要粉刷第i个房子
        //不妨第(i - 1)个房子粉刷成红色时花费最少，为preRedCost；而粉刷成蓝色是花费第二少，为preBlueCost
        //1. 如果第i个房子粉刷成红色，花费为r，则此时将前i个房子粉刷好的最小花费是(r + preBlueCost)
        //2. 如果第i个房子粉刷成非红色，花费为a，则此时将前i个房子粉刷好的最小花费是(a + preRedCost)

        //只需要维护前(i - 1)个房子的最小花费和第二小花费，以及最小花费时第(i - 1)个房子的颜色即可
        int preMinCost = 0, preMinCostIdx = -1, preSecondMinCost = 0;

        for(int[] cur: costs){
            int curMinCost = Integer.MAX_VALUE, curMinCostIdx = -1, curSecondMinCost = Integer.MAX_VALUE;
            
            for(int j = 0; j < cur.length; j++){
                
                //计算出当前房子粉刷成第j种颜色时的花费
                cur[j] += j == preMinCostIdx ? preSecondMinCost : preMinCost;
                
                //更新当前房子的最小花费等数据
                if(cur[j] < curMinCost){
                    curSecondMinCost = curMinCost;
                    curMinCost = cur[j];
                    curMinCostIdx = j;
                } else if(cur[j] < curSecondMinCost){
                    curSecondMinCost = cur[j];
                }
            }
            
            //为下次循环做准备
            preMinCost = curMinCost;
            preMinCostIdx = curMinCostIdx;
            preSecondMinCost = curSecondMinCost;
        }
        
        return preMinCost;
    }
}