题目:
房屋染色
题目描述
假如有一排房子,共 n 个,每个房子可以被粉刷成红色、粉色或者绿色这三种颜色中的一种,小码君想了一想,想把每两个相邻的房子颜色刷成不同的。他现在开始准备给这n个房子房子涂油漆了。然后发现涂第i个房子的油漆花费是不一样的,给第i个房子涂成红、粉、绿三种颜色的花费分别是cost[i][0],cost[i][1],cost[i][2];现在小码君想知道,按照他这种要求,最少需要花费多少钱去给这些房子涂上油漆呢?
提示
样例说明:三个屋子分别选择第1、2、1种颜色,此时总花费是10.
输入格式
输入一个整数 n(0<n≤500),代表房子的总数。接下来输入一个N∗N的矩阵表示涂成每种房子需要的花费
输出格式
输出一个整数,代表最少需要花费多少钱。
样例组输入#1
3
14 2 11
11 14 5
14 3 10
样例组输出#1
10
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
AI回复:
为了计算最小的涂漆费用,我们可以使用动态规划的方法。以下是详细的 C++ 实现,解决了这个问题,并且不使用 vector,只使用普通数组。
题目分析
我们需要保证相邻的房子颜色不同,并且使得总的涂漆成本最小。可以用动态规划来解决这个问题。我们定义 dp[i][j] 为涂到第 i 个房子且第 i 个房子颜色为 j 时的最小费用,其中 j 的取值为 0 (红色), 1 (粉色), 2 (绿色)。
动态规划转移方程
* 初始化第一个房子的费用,直接赋值为涂第一个房子的费用。
* 对于每个后续房子,计算涂上每种颜色的最小成本,确保相邻房子的颜色不同:
* dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0]
* dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1]
* dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2]
最终结果
计算最后一个房子的三种颜色的费用的最小值,即 min(dp[n-1][0], dp[n-1][1], dp[n-1][2])。
C++ 实现
以下是使用纯数组的 C++ 代码:
代码解释
1. 输入处理:读取房屋数 n 和每个房子涂成不同颜色的成本。
2. 动态规划初始化:初始化第一个房子的涂漆费用。
3. 动态规划状态转移:根据相邻房子颜色不同的要求更新 DP 表。
4. 输出结果:输出最后一个房子的三种颜色的最小费用。
使用这种方法可以有效地解决问题,保证相邻房子的颜色不同并最小化总费用。
结果: