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

113 阅读 0 评论 75 点赞

我是靠谱客的博主大胆路人，这篇文章主要介绍粉刷房子（逆向思维+弯道超车），现在分享给大家，希望可以做个参考。

废话不多说，直奔主题。

⭐题目详情

假如有一排房子，共 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 };
1
2
3
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 };
1
2
3
4
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)......

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

⭐核心代码

复制代码

1
2
3
4
5
6
for(int i=1;i<n;i++){
redCosts[i]+=Math.min(blueCosts[i-1],greenCosts[i-1]);
blueCosts[i]+=Math.min(redCosts[i-1],greenCosts[i-1]);
greenCosts[i]+=Math.min(redCosts[i-1],blueCosts[i-1]);
}
return Math.min(redCosts[n-1],Math.min(blueCosts[n-1],greenCosts[n-1] ) );

⭐代码汇总

复制代码

public class 粉刷房子 {
// 求粉刷房子的最小成本
// n: 房屋的数量
// redCosts[i]表示房屋[i]需要粉刷成红色所需要的价钱，blueCosts、greenCosts同理
public int minCost(int n, int[] redCosts, int[] blueCosts, int[] greenCosts) {
for(int i=1;i<n;i++){
redCosts[i]+=Math.min(blueCosts[i-1],greenCosts[i-1]);
blueCosts[i]+=Math.min(redCosts[i-1],greenCosts[i-1]);
greenCosts[i]+=Math.min(redCosts[i-1],blueCosts[i-1]);
}
return Math.min(redCosts[n-1],Math.min(blueCosts[n-1],greenCosts[n-1] ) );
}
public static void main(String[] args) {
动态规划.粉刷房子 sln = new 动态规划.粉刷房子();
int n1 = 3;
int[] redCosts1 = { 17, 16, 14 }; // 用红色刷第0、1、2号房屋的成本分别是17、16、14
int[] blueCosts1 = { 2, 1, 3 }; // 用蓝色刷每个房屋的成本
int[] greenCosts1 = { 17, 10, 19 }; // 用绿色刷每个房屋的成本
int ans1 = sln.minCost(n1, redCosts1, blueCosts1, greenCosts1);
System.out.println("测试用例1 我的答案: " + ans1 + " 正确答案: 15n");
int n2 = 13;
int[] redCosts2 = { 10, 5, 6, 6, 17, 7, 8, 18, 3, 13, 1, 18, 10 };
int[] blueCosts2 = { 14, 10, 16, 20, 15, 13, 17, 4, 13, 11, 11, 3, 4 };
int[] greenCosts2 = { 14, 1, 14, 13, 16, 5, 6, 1, 4, 17, 3, 1, 9 };
int ans2 = sln.minCost(n2, redCosts2, blueCosts2, greenCosts2);
System.out.println("测试用例2 我的答案: " + ans2 + " 正确答案: 79n");
int n3 = 9;
int[] redCosts3 = { 1, 4, 6, 14, 6, 8, 13, 1, 7 }; // 用红色刷第0、1、2号房屋的成本分别是17、16、14
int[] blueCosts3 = {
7, 19, 9, 10, 11, 5, 10, 5, 18}; // 用蓝色刷每个房屋的成本
int[] greenCosts3 = { 15, 8, 20, 7, 4, 8, 9, 15,18 }; // 用绿色刷每个房屋的成本
int ans3 = sln.minCost(n3, redCosts3, blueCosts3, greenCosts3);
System.out.println("测试用例3 我的答案: " + ans3 + " 正确答案: 54n");
int n4 = 100;
int[] redCosts4 = { 1, 4, 6, 14, 6, 8, 13, 1, 7, 2, 14, 13, 15, 14, 5, 11, 3, 13, 7, 17, 3, 19, 5, 12, 10, 15, 15, 17, 3, 11, 5, 6, 14, 16, 6, 10, 4, 8, 12, 16, 2, 2, 2, 13, 3, 2, 15, 16, 11, 11, 2, 10, 11, 9, 3, 9, 15, 3, 5, 12, 9, 16, 17, 8, 19, 16, 10, 6, 19, 14, 14, 1, 15, 8, 8, 18, 5, 7, 10, 5, 19, 16, 14, 18, 13, 2, 16, 12, 17, 12, 2, 17, 4, 10, 11, 14, 20, 4, 8, 5 };
int[] blueCosts4 = { 7, 19, 9, 10, 11, 5, 10, 5, 18, 17, 12, 8, 2, 10, 13, 18, 5, 8, 5, 3, 4, 3, 12, 2, 10, 1, 8, 2, 11, 20, 15, 2, 2, 11, 6, 15, 11, 12, 3, 19, 9, 18, 17, 7, 11, 4, 7, 8, 4, 10, 12, 18, 13, 7, 16, 9, 7, 7, 13, 17, 5, 13, 7, 17, 7, 4, 20, 18, 11, 6, 9, 9, 18, 6, 13, 5, 19, 19, 11, 10, 16, 12, 3, 11, 14, 10, 4, 13, 11, 15, 1, 17, 13, 8, 20, 15, 4, 18, 3, 3 };
int[] greenCosts4 = { 15, 8, 20, 7, 4, 8, 9, 15, 18, 13, 6, 17, 4, 2, 5, 4, 8, 18, 3, 11, 5, 10, 15, 9, 1, 8, 8, 2, 20, 8, 8, 14, 10, 14, 6, 3, 14, 11, 11, 14, 17, 17, 13, 13, 9, 4, 4, 20, 5, 1, 1, 1, 4, 14, 4, 4, 8, 14, 9, 7, 1, 20, 1, 1, 6, 18, 18, 13, 20, 3, 13, 14, 17, 4, 11, 9, 3, 6, 14, 19, 10, 17, 13, 12, 10, 20, 5, 8, 8, 17, 2, 12, 11, 6, 6, 19, 2, 17, 12, 9 };
int ans4 = sln.minCost(n4, redCosts4, blueCosts4, greenCosts4);
System.out.println("测试用例4 我的答案: " + ans4 + " 正确答案: 627n");
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class 粉刷房子 {
// 求粉刷房子的最小成本
// n: 房屋的数量
// redCosts[i]表示房屋[i]需要粉刷成红色所需要的价钱，blueCosts、greenCosts同理
public int minCost(int n, int[] redCosts, int[] blueCosts, int[] greenCosts) {
for(int i=1;i<n;i++){
redCosts[i]+=Math.min(blueCosts[i-1],greenCosts[i-1]);
blueCosts[i]+=Math.min(redCosts[i-1],greenCosts[i-1]);
greenCosts[i]+=Math.min(redCosts[i-1],blueCosts[i-1]);
}
return Math.min(redCosts[n-1],Math.min(blueCosts[n-1],greenCosts[n-1] ) );
}
public static void main(String[] args) {
动态规划.粉刷房子 sln = new 动态规划.粉刷房子();
int n1 = 3;
int[] redCosts1 = { 17, 16, 14 }; // 用红色刷第0、1、2号房屋的成本分别是17、16、14
int[] blueCosts1 = { 2, 1, 3 }; // 用蓝色刷每个房屋的成本
int[] greenCosts1 = { 17, 10, 19 }; // 用绿色刷每个房屋的成本
int ans1 = sln.minCost(n1, redCosts1, blueCosts1, greenCosts1);
System.out.println("测试用例1 我的答案: " + ans1 + " 正确答案: 15n");
int n2 = 13;
int[] redCosts2 = { 10, 5, 6, 6, 17, 7, 8, 18, 3, 13, 1, 18, 10 };
int[] blueCosts2 = { 14, 10, 16, 20, 15, 13, 17, 4, 13, 11, 11, 3, 4 };
int[] greenCosts2 = { 14, 1, 14, 13, 16, 5, 6, 1, 4, 17, 3, 1, 9 };
int ans2 = sln.minCost(n2, redCosts2, blueCosts2, greenCosts2);
System.out.println("测试用例2 我的答案: " + ans2 + " 正确答案: 79n");
int n3 = 9;
int[] redCosts3 = { 1, 4, 6, 14, 6, 8, 13, 1, 7 }; // 用红色刷第0、1、2号房屋的成本分别是17、16、14
int[] blueCosts3 = {
7, 19, 9, 10, 11, 5, 10, 5, 18}; // 用蓝色刷每个房屋的成本
int[] greenCosts3 = { 15, 8, 20, 7, 4, 8, 9, 15,18 }; // 用绿色刷每个房屋的成本
int ans3 = sln.minCost(n3, redCosts3, blueCosts3, greenCosts3);
System.out.println("测试用例3 我的答案: " + ans3 + " 正确答案: 54n");
int n4 = 100;
int[] redCosts4 = { 1, 4, 6, 14, 6, 8, 13, 1, 7, 2, 14, 13, 15, 14, 5, 11, 3, 13, 7, 17, 3, 19, 5, 12, 10, 15, 15, 17, 3, 11, 5, 6, 14, 16, 6, 10, 4, 8, 12, 16, 2, 2, 2, 13, 3, 2, 15, 16, 11, 11, 2, 10, 11, 9, 3, 9, 15, 3, 5, 12, 9, 16, 17, 8, 19, 16, 10, 6, 19, 14, 14, 1, 15, 8, 8, 18, 5, 7, 10, 5, 19, 16, 14, 18, 13, 2, 16, 12, 17, 12, 2, 17, 4, 10, 11, 14, 20, 4, 8, 5 };
int[] blueCosts4 = { 7, 19, 9, 10, 11, 5, 10, 5, 18, 17, 12, 8, 2, 10, 13, 18, 5, 8, 5, 3, 4, 3, 12, 2, 10, 1, 8, 2, 11, 20, 15, 2, 2, 11, 6, 15, 11, 12, 3, 19, 9, 18, 17, 7, 11, 4, 7, 8, 4, 10, 12, 18, 13, 7, 16, 9, 7, 7, 13, 17, 5, 13, 7, 17, 7, 4, 20, 18, 11, 6, 9, 9, 18, 6, 13, 5, 19, 19, 11, 10, 16, 12, 3, 11, 14, 10, 4, 13, 11, 15, 1, 17, 13, 8, 20, 15, 4, 18, 3, 3 };
int[] greenCosts4 = { 15, 8, 20, 7, 4, 8, 9, 15, 18, 13, 6, 17, 4, 2, 5, 4, 8, 18, 3, 11, 5, 10, 15, 9, 1, 8, 8, 2, 20, 8, 8, 14, 10, 14, 6, 3, 14, 11, 11, 14, 17, 17, 13, 13, 9, 4, 4, 20, 5, 1, 1, 1, 4, 14, 4, 4, 8, 14, 9, 7, 1, 20, 1, 1, 6, 18, 18, 13, 20, 3, 13, 14, 17, 4, 11, 9, 3, 6, 14, 19, 10, 17, 13, 12, 10, 20, 5, 8, 8, 17, 2, 12, 11, 6, 6, 19, 2, 17, 12, 9 };
int ans4 = sln.minCost(n4, redCosts4, blueCosts4, greenCosts4);
System.out.println("测试用例4 我的答案: " + ans4 + " 正确答案: 627n");
}
}