265. Paint House II 房屋涂不同颜色的油漆
2021/11/1 6:09:58
本文主要是介绍265. Paint House II 房屋涂不同颜色的油漆,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
There are a row of n
houses, each house can be painted with one of the k
colors. 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 an n x k
cost matrix costs.
- For example,
costs[0][0]
is the cost of painting house0
with color0
;costs[1][2]
is the cost of painting house1
with color2
, and so on...
Return the minimum cost to paint all houses.
Example 1:
Input: costs = [[1,5,3],[2,9,4]] Output: 5 Explanation: Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5.
Example 2:
Input: costs = [[1,3],[2,4]] Output: 5 参考:https://leetcode.com/problems/paint-house-ii/discuss/69502/Evolve-from-brute-force-to-optimal
This is similar to paint house.
- O((k-1)^n) brute force
int minCostII(vector<vector<int>>& costs) { if(costs.empty()) return 0; return minCost(-1,-1,costs); } int minCost(int i,int j, vector<vector<int>>& costs) { //minCost starting from house i with color j if(i==costs.size()) return 0; int mc = INT_MAX; for(int k=0;k<costs[0].size();k++) if(k!=j) mc = min(mc, minCost(i+1,k,costs)); return i<0? mc : mc+costs[i][j]; }
- O(nk^2) Memoization
int minCostII(vector<vector<int>>& costs) { if(costs.empty()) return 0; vector<vector<int>> mem(costs.size(),vector<int>(costs[0].size())); return minCost(-1,-1,mem,costs); } int minCost(int i,int j, vector<vector<int>>& mem, vector<vector<int>>& costs) { if(i==costs.size()) return 0; if(i>0 && mem[i][j]) return mem[i][j]; int mc = INT_MAX; for(int k=0;k<costs[0].size();k++) if(k!=j) mc = min(mc, minCost(i+1,k,mem,costs)); return i<0? mc : mem[i][j]=mc+costs[i][j]; }
- O(nk^2) dp
int minCostII(vector<vector<int>>& costs) { if(costs.empty()) return 0; int n = costs.size(), k = costs[0].size(); vector<vector<int>> dp(n+1,vector<int>(k)); for(int i=n-1;i>=0;i--) for(int j=0;j<k;j++) dp[i][j]=getMin(j,dp[i+1]) + costs[i][j]; return getMin(-1, dp[0]); } int getMin(int j, vector<int> &pre) { int mc = INT_MAX; for(int i=0;i<pre.size();i++) if(i!=j) mc = min(mc,pre[i]); return mc; }
- O(nk) dp
int minCostII(vector<vector<int>>& costs) { int pre1=0,pre2=0,c1=-1; for(auto &v:costs) { int cur1=INT_MAX,cur2,co1; for(int i=0;i<v.size();i++) { int c = v[i]+ (i==c1?pre2:pre1); if(c<cur1) { cur2 = cur1; co1 = i; cur1 = c; } else if (c<cur2) cur2 = c; } pre1 = cur1; pre2 = cur2; c1 = co1; } return pre1; }
这篇关于265. Paint House II 房屋涂不同颜色的油漆的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-15Tailwind开发入门教程:从零开始搭建第一个项目
- 2024-11-14Emotion教程:新手入门必备指南
- 2024-11-14音频生成的秘密武器:扩散模型在音乐创作中的应用
- 2024-11-14从数据科学家到AI开发者:2023年构建生成式AI网站应用的经验谈
- 2024-11-14基于AI的智能调试助手创业点子:用代码样例打造你的调试神器!
- 2024-11-14受控组件学习:从入门到初步掌握
- 2024-11-14Emotion学习入门指南
- 2024-11-14Emotion学习入门指南
- 2024-11-14获取参数学习:初学者指南
- 2024-11-14受控组件学习:从入门到实践