公司的网站怎么建设,汉中公司做网站,查询战网,宁德市住房和城乡建设局网站文章目录1. 题目2. 解题1. 题目
假如有一排房子#xff0c;共 n 个#xff0c;每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种#xff0c;你需要粉刷所有的房子并且使其与相邻的两个房子颜色不能相同。
当然#xff0c;因为市场上不同颜色油漆的价格不同共 n 个每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种你需要粉刷所有的房子并且使其与相邻的两个房子颜色不能相同。
当然因为市场上不同颜色油漆的价格不同所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的矩阵来表示的。
例如costs[0][0] 表示第 0 号房子粉刷成红色的成本花费costs[1][2] 表示第 1 号房子粉刷成绿色的花费以此类推。请你计算出粉刷完所有房子最少的花费成本。
注意
所有花费均为正整数。示例
输入: [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色1 号房子粉刷成绿色2 号房子粉刷成蓝色。最少花费: 2 5 3 10。来源力扣LeetCode 链接https://leetcode-cn.com/problems/paint-house 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目LeetCode 265. 粉刷房子 IIDP
dp[i][c] 表示刷完 i 房子后i 房子是 c 颜色时花费最小多少
class Solution {
public:int minCost(vectorvectorint costs) {int n costs.size(), house, color;if(n0) return 0;vectorvectorint dp(n,vectorint(3,INT_MAX));dp[0] costs[0];for(house 1; house n; house){for(color 0; color 3; color){dp[house][color] min(dp[house][color], costs[house][color]min(dp[house-1][(color1)%3], dp[house-1][(color2)%3]));}}return min(dp[n-1][0], min(dp[n-1][1], dp[n-1][2]));}
};12 ms 9.5 MB 长按或扫码关注我的公众号一起加油、一起学习进步
