a做爰视频免费网站,wordpress公众号导航主题,重庆网站建设找珊瑚云,旅游网站信息门户建设方案LCR 091. 粉刷房子https://leetcode.cn/problems/JEj789/description/
假如有一排房子#xff0c;共n个#xff0c;每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种#xff0c;你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。当然#xff0c;因为市…LCR 091. 粉刷房子https://leetcode.cn/problems/JEj789/description/
假如有一排房子共n个每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。当然因为市场上不同颜色油漆的价格不同所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个n x 3的正整数矩阵costs来表示的。例如costs[0][0]表示第0号房子粉刷成红色的成本花费costs[1][2]表示第1号房子粉刷成绿色的花费以此类推。请计算出粉刷完所有房子最少的花费成本。
输入costs [[17,2,17],[16,16,5],[14,3,19]]输出10解释将0号房子粉刷成蓝色1号房子粉刷成绿色2号房子粉刷成蓝色。最少花费2 5 3 10。输入costs [[7,6,2]]输出2
提示costs.length ncosts[i].length 31 n 1001 costs[i][j] 20。 我们用动态规划的思想来解决这个问题。
确定状态表示根据经验和题目要求我们用dp[i]表示粉刷完i位置的房子后此时的最少花费。这可以细分为
用dp[i][0]表示将i位置的房子粉刷成红色之后的最少花费。用dp[i][1]表示将i位置的房子粉刷成蓝色之后的最少花费。用dp[i][2]表示将i位置的房子粉刷成绿色之后的最少花费。
简单来说在dp[i][j]中i表示最后一个粉刷的房子的编号j表示最后一个粉刷的房子中粉刷的颜色的编号dp[i][j]表示此时的最少花费。
推导状态转移方程我们考虑最近的一步即粉刷完i - 1位置的房子之后的情况。
考虑dp[i][0]。把i位置的房子粉刷成红色所以只能把i - 1位置的房子粉刷成蓝色或者绿色。那么把i位置的房子粉刷成红色之后的最少花费就应该是把i - 1位置的房子粉刷成蓝色或者绿色之后的最少花费两种情况的较小值再加上把i位置粉刷成红色的花费。即dp[i][0] min(dp[i - 1][1], dp[i - 1][2]) costs[i][0]。同理dp[i][1] min(dp[i - 1][0], dp[i - 1][2]) costs[i][1]dp[i][2] min(dp[i - 1][0], dp[i - 1][1]) costs[i][2]。
综上所述dp[i][0] min(dp[i - 1][1], dp[i - 1][2]) costs[i][0]dp[i][1] min(dp[i - 1][0], dp[i - 1][2]) costs[i][1]dp[i][2] min(dp[i - 1][0], dp[i - 1][1]) costs[i][2]。
初始化根据状态转移方程在计算dp[0][j]其中j的范围是[0, 2]时会发生越界访问所以要进行相应的初始化。
dp[0][0]表示把0位置的房子粉刷成红色后此时的最少花费显然dp[0][0] costs[0][0]。同理dp[0][1] costs[0][1]dp[0][2] costs[0][2]。
综上所述dp[0][0] costs[0][0]dp[0][1] costs[0][1]dp[0][2] costs[0][2]。
当然我们可以在最前面添加一个辅助结点dp[0][j] 0其中j的范围是[0, 2]。这样根据状态转移方程以dp[i][0]为例此时min(dp[0][1], dp[0][2]) 0辅助结点的值不影响结果符合预期。
填表顺序根据状态转移方程对于dp[i][j]只依赖于dp[i - 1][j]j的范围是[0, 2]。那么我们只需要沿着i增大的方向填表。
返回值由于不确定把最后一个房子粉刷成什么颜色根据状态表示最终应返回把最后一个房子粉刷成红色、蓝色或者绿色这3种情况中最少花费的最小值即dp[n][j]的最小值其中j的范围是[0, 2]。
细节问题由于新增了一个辅助结点此时dp表的规模就不是n x 3而是(n 1) x 3。同时需注意下标的映射关系dp[i][j]对应的是costs[i - 1][j]。
时间复杂度O(N)空间复杂度O(N)。
class Solution {
public:int minCost(vectorvectorint costs) {int n costs.size();// 创建dp表vectorvectorint dp(n 1, vectorint(3));// 填表for (int i 1; i n; i) {dp[i][0] min(dp[i - 1][1], dp[i - 1][2]) costs[i - 1][0];dp[i][1] min(dp[i - 1][0], dp[i - 1][2]) costs[i - 1][1];dp[i][2] min(dp[i - 1][0], dp[i - 1][1]) costs[i - 1][2];}// 返回结果return min(dp[n][0], min(dp[n][1], dp[n][2]));}
};
