[leetcode] 256 Paint House

[leetcode] 256 Paint House

Description

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Note: All costs are positive integers.

分析

题目的意思是：给n个房子涂颜色，相邻的房子颜色不能一样，涂每种颜色的代价不一样，求最小代价。

dp[i][j]表示刷到第i+1房子用的颜色的花费。dp[i][j] = dp[i][j] + min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3])如果当前的房子要用红色刷，那么上一个房子只能用绿色或蓝色来刷，那么我们要求刷到当前房子，且当前房子用红色刷的最小花费就等于当前房子用红色刷的钱加上刷到上一个房子用绿色和刷到上一个房子用蓝色的较小值，这样当我们算到最后一个房子时，我们只要取出三个累计花费的最小值即可

代码

class Solution {public: int minCost(vector>& costs) { if (costs.empty() || costs[0].empty()) return 0; vector> dp = costs; for (int i = 1; i < dp.size(); ++i) { for (int j = 0; j < 3; ++j) { dp[i][j] += min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]); } } return min(min(dp.back()[0], dp.back()[1]), dp.back()[2]); }};

参考文献

​​[LeetCode] Paint House 粉刷房子​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。