『LeetCode|每日一题』----＞粉刷房子

目录

1.每日一句

2.作者简介

『LeetCode|每日一题』粉刷房子

1.每日一题

2.解题思路 

        2.1 思路分析

        2.2 核心代码

        2.3 完整代码

        2.4 运行结果 

---

1.每日一句

玫瑰与晚霞共绘浪漫，你是我心里的爱意泛滥

2.作者简介

🏡个人主页：XiaoXiaoChen-2716

📚学习专栏：力扣专栏   

🕒发布日期：2022/11/8

『LeetCode|每日一题』粉刷房子

1.每日一题

原文链接--->点我

2.解题思路 

        2.1 思路分析

此题提到相邻的房子不能粉刷同样的颜色，所以是一个经典的动态规划题

        S1：首先需要定义一个dp数组，我把它定义为二维的，dp[i][j]表示从第0号到第i号房子同时第j号房子被粉刷j号颜色的最小花费；

        S2：第二步就需要初始化dp数组，只需要初始化第0号房子的费用即可，很容易理解dp[0][i] = costs[0][i]；

        S3：接下来就是利用状态转化公式，由于相邻两间房的颜色不能相同，也就可以这么写： 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][0] , dp[i - 1][1]) + costs[i][2];

拿第一行代码来解释，第i号放间如果是0号颜色，那么它的价格就要用第i-1号房间的1号或者2号颜色才符合题目要求；

        S4：最后看从0号房间到len-1号房间且第len-1号房间上什么颜色的费用最少，就选择那种方式

        2.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][0] , dp[i - 1][1]) + costs[i][2];
        }

        2.3 完整代码

class Solution {
    public int minCost(int[][] costs) {
        int len = costs.length;
        int[][] dp = new int[len + 1][3];
        //初始化
        for(int i = 0 ; i < 3 ; i++){
            dp[0][i] = costs[0][i];
        } 
        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][0] , dp[i - 1][1]) + costs[i][2];
        }
        return Math.min(Math.min(dp[len - 1][0] , dp[len - 1][1]) , dp[len - 1][2]);
    }
}

        2.4 运行结果

---

🍁 类似题目推荐：

1.数据结构基础 

2.算法专项练习 

3.剑指offer专项练习

4.推荐一个学习网站：LeetCode，算法的提升在于日积月累，只有每天练习才能保持良好的状态

如果文章对各位大佬有帮助就支持一下噢，不好的地方请各位大佬多多指教！