粉刷房子（逆向思维+弯道超车）

废话不多说，直奔主题。

⭐题目详情

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。我们将给出一个正整数n，表示房子的数量，以及三个长度为n的数组redCosts, blueCosts，greenCosts，用来表示每个房子粉刷成对应颜色的花费。

例如，redCosts[0] 表示第 0 号房子粉刷成红色的成本花费；greenCosts[2] 表示第 2 号房子粉刷成绿色的花费，以此类推。

请计算出在给出的条件限制下，粉刷完所有房子最少的花费成本。

本题应当满足n<=1000000时可解（并在合理时间内返回）

⭐例子1

int[] redCosts1 = { 17, 16, 14 }; 
int[] blueCosts1 = { 2, 1, 3 }; 
int[] greenCosts1 = { 17, 10, 19 }; 

正确答案：15

⭐例子2

int[] redCosts4 = { 1, 4, 6, 14, 6, 8, 13, 1, 7 }; 
int[] blueCosts4 = {  7, 19, 9, 10, 11, 5, 10, 5, 18}; 
int[] greenCosts4 = { 15, 8, 20, 7, 4, 8, 9, 15,18 };

正确答案：54（易错答案：61）❗看看是不是你中招了（弯道超车体现在这）

看看过程吧😵

⭐核心思路

如上图所示，4+min(7,15),19+min(1,15)......

就是加上一行不同列的最小值

⭐核心代码

for(int i=1;i

public class 粉刷房子 {// 求粉刷房子的最小成本// n: 房屋的数量// redCosts[i]表示房屋[i]需要粉刷成红色所需要的价钱，blueCosts、greenCosts同理public int minCost(int n, int[] redCosts, int[] blueCosts, int[] greenCosts) {for(int i=1;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！