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-20实战:30 行代码做一个网页端的 AI 聊天助手
- 2024-11-185分钟搞懂大模型的重复惩罚后处理
- 2024-11-18基于Ollama和pgai的个人知识助手项目:用Postgres和向量扩展打造智能数据库
- 2024-11-15我用同一个提示测试了4款AI工具,看看谁设计的界面更棒
- 2024-11-15深度学习面试的时候,如何回答1x1卷积的作用
- 2024-11-15检索增强生成即服务:开发者的得力新帮手
- 2024-11-15技术与传统:人工智能时代的最后一袭纱丽
- 2024-11-15未结构化数据不仅仅是给嵌入用的:利用隐藏结构提升检索性能
- 2024-11-15Emotion项目实战:新手入门教程
- 2024-11-157 个开源库助你构建增强检索生成(RAG)、代理和 AI 搜索